https://leetcode-cn.com/problems/combination-sum/
真的没想到这么短的一个程序写了还挺久，而且程序效率还不高。 有很大一部分原因是对 Go 的切片理解不充分，再加上早晨起来大脑比较懵。
对 Go 的切片可以参考这篇文章
程序的主要思路是对各种情况进行递归探索，实际上复杂度已经到了 O(n!)，感觉不是很妙。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func getAllComs(candidates []int, target int, nowPos int, nowSlice *[]int, nowSum int, ret *[][]int) {
s:=nowSum+candidates[nowPos]
switch {
case s==target:
*nowSlice=append(*nowSlice,candidates[nowPos])
*ret=append(*ret,*nowSlice)
return
case s>target:
return
case s<target:
*nowSlice=append(*nowSlice,candidates[nowPos])
for i:=nowPos;i<len(candidates);i++ {
ns:=make([]int,len(*nowSlice))
copy(ns,*nowSlice)
getAllComs(candidates,target,i,&ns,s,ret)
}
}
}
func combinationSum(candidates []int, target int) [][]int {
var ret [][]int
for i:=0;i<len(candidates);i++ {
nowSlice:=make([]int,0)
getAllComs(candidates,target,i,&nowSlice,0,&ret)
}
return ret
}
|
看了一下别人的方法，大同小异，但是别人的代码就很快，而且很简洁，在这里学习一下。
他的思路是先排序，然后每次循环当前字符后面的那部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func getAllComs(candidates []int, nowTarget int, nowSlice []int, ret *[][]int) {
for i,v:=range candidates {
switch {
case v==nowTarget:
nowSlice=append(nowSlice,candidates[i])
temp:=make([]int,len(nowSlice))
copy(temp,nowSlice)
*ret=append(*ret,temp)
case v<nowTarget:
getAllComs(candidates[i:],nowTarget-v,append(nowSlice,candidates[i]),ret)
default:
return
}
}
}
func combinationSum(candidates []int, target int) [][]int {
var ret [][]int
sort.Ints(candidates)
getAllComs(candidates,target,[]int{},&ret)
return ret
}
|
下面是一个简单的C++回溯版本，在这个版本中，不必关心每一个元素的顺序，只需要不走回头路即可。但是因为递归调用层次会很多，所以需要时间和空间都比较大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
void getAll(vector<int>& candidates, int target, vector<vector<int>>& result, vector<int> record, int pos) {
if(target < 0) return;
if(target == 0) {
vector<int> record_copy(record);
result.push_back(record_copy);
return;
}
for(int i=pos; i<candidates.size(); ++i) {
int c = candidates[i];
record.push_back(c);
getAll(candidates, target-c, result, record, i);
record.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> record;
getAll(candidates, target, result, record, 0);
return result;
}
};
|
下面是一个优化的版本，先通过sort函数对candidates数组进行排序，然后再行回溯，这时，因为有了大小的假设，就可以在循环中对一些情况进行判断，如果出现问题及时推出循环，减少了很多循环次数，并且不必再次递归调用函数，效率会提升很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
void getAll(vector<int>& candidates, int target, vector<vector<int>>& result, vector<int> record, int pos) {
for(int i=pos; i<candidates.size(); ++i) {
int c = candidates[i];
int t = target-c;
if(t < 0) return;
else if(t == 0) {
vector<int> record_copy(record);
record_copy.push_back(c);
result.push_back(record_copy);
return;
} else {
record.push_back(c);
getAll(candidates, t, result, record, i);
record.pop_back();
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> record;
sort(candidates.begin(), candidates.end());
getAll(candidates, target, result, record, 0);
return result;
}
};
|
最后一种解法很有意思，它没有采用回溯的思想，而是采用了dp的思路，方法参考了https://leetcode-cn.com/problems/combination-sum/solution/chao-qiang-gifzhu-ni-shi-yong-dong-tai-gui-hua-qiu/。
首先，使用一个map记录1到target中每一个数的解作为历史记录。然后，通过不断循环（1到target）来得到中间每个target的结果。
在外层循环中还有一个内层循环，内存循环主要寻找candidates里可以插入到当前target对应数组的数据。如果某个candidate和i相等，则说明它可以作为结果数据，这些数据就是起始值。如果i大于某个candidate，则可以寻找i-c，如果找到，就说明i的结果可以用之前的数据构建，就将之前的数据插入record[i]中。
最终，将record[i]中的元素转移到一个vector中返回即可。
需要注意的是去重，这里用set<vector<int>>以及使用sort(r.begin(), r.end())都是为了去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
unordered_map<int, set<vector<int>>> record;
for(int i=1; i<=target; ++i) {
for(int c:candidates) {
if(i == c) {
record[c].insert(vector<int>{c});
} else if(i > c) {
for(auto r:record[i-c]) {
r.push_back(c);
sort(r.begin(), r.end());
if(record[i].count(r)==0) {
record[i].insert(r);
}
}
}
}
}
vector<vector<int>> result;
for(auto r:record[target]) result.push_back(r);
return result;
}
};
|