https://leetcode-cn.com/problems/combination-sum-ii/
感觉和上一题思路很相似， 只要不重复当前的那个数字就可以，但是由于数字会重复， 这就导致可能出现重复的结果，所以使用了一个哈希表来去重。
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
| import "fmt"
func getAllCombs(candidates []int, nowTarget int, nowSlice []int,ret *[][]int,resMap map[string]bool){
for i,v :=range candidates{
switch {
case v==nowTarget:
temp:=make([]int,len(nowSlice))
copy(temp,nowSlice)
temp=append(temp,v)
tempStr:=fmt.Sprint(temp)
if _,ok:=resMap[tempStr];!ok {
resMap[tempStr]=true
*ret=append(*ret,temp)
}
case v<nowTarget:
getAllCombs(candidates[i+1:],nowTarget-v,append(nowSlice,v),ret,resMap)
default:
return
}
}
}
func combinationSum2(candidates []int, target int) [][]int {
resMap:=make(map[string]bool)
var ret [][]int
sort.Ints(candidates)
getAllCombs(candidates,target,[]int{},&ret,resMap)
return ret
}
|
但是因为使用了一个 fmt 包，导致效率不够高。
看了一下其他答案的思路，发现当时也想到了，但就差那么一点点逻辑不是太对就没用 T_T 。
不过也算是复习一下 go 语言中 fmt 包和 map 的用法吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func getAllCombs(candidates []int, nowTarget int, nowSlice []int,ret *[][]int){
for i,v :=range candidates{
if i>0 && v==candidates[i-1] {
continue
}
switch {
case v==nowTarget:
temp:=make([]int,len(nowSlice))
copy(temp,nowSlice)
temp=append(temp,v)
*ret=append(*ret,temp)
case v<nowTarget:
getAllCombs(candidates[i+1:],nowTarget-v,append(nowSlice,v),ret)
default:
return
}
}
}
func combinationSum2(candidates []int, target int) [][]int {
var ret [][]int
sort.Ints(candidates)
getAllCombs(candidates,target,[]int{},&ret)
return ret
}
|
以下是毫无新意的C++版本，和上一题有两点不同，一个是不能采用用过的元素，所以添加了一个pos参数，将用过的元素跳过，第二个是如果出现相同的元素需要去重，一个方案是通过set，另一个方案是下面答案中的判断if(i>pos && candidates[i-1] == c) continue;，它的作用是如果之前用过这个元素，那就跳过它。
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];
if(i>pos && candidates[i-1] == c) continue;
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+1);
record.pop_back();
}
}
}
vector<vector<int>> combinationSum2(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;
}
};
|