40. Combination Sum II

题目

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

题意

同39题,只不过不能重复选元素,而且给定的集合中有重复的元素,这个涉及到了列表中包含列表的去重问题
我的解法同39题,只是将其中每次递归时的i增加了

第二遍 java实现

python实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = []
res=[]
out=0
index=-1
candidates=sorted(candidates)
#print(candidates)
result,res,out=self.digui(0,res,out,target,candidates,result)
for i in range(len(result)):
j=i+1;
while j<len(result):
if result[i]==result[j]:
result.pop(j)
else:j+=1
return result
def digui(self,i,res,out,target,candidates,result):
while i<len(candidates):
if out+candidates[i]>=target:
if out+candidates[i]==target:
temp = [k for k in res]
temp.append(candidates[i])
result.append(temp)
if len(res)>0:
out -= res[-1]
res.pop(-1)
return result,res,out
else:
out+=candidates[i]
res.append(candidates[i])
result,res,out=self.digui(i+1,res,out,target,candidates,result)
i+=1
if len(res)>0:
out -= res[-1]
res.pop(-1)
return result,res,out

Java实现

注意对重复元素的处理,当前for循环中如果再次遍历到相同的元素需要跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list=new ArrayList<List<Integer>>();
Arrays.sort(candidates);
List<Integer> arr=new ArrayList<>();
getList(list,arr,candidates,0,0,target);
return list;
}
public void getList(List<List<Integer>> list,List<Integer> arr,int[] candidates,int cur,int i,int target){
if(cur==target){
list.add(new ArrayList<Integer>(arr));
}else if(cur<target){
for(int j=i;j<candidates.length&&cur+candidates[j]<=target;j++){
if(j>i&&candidates[j]==candidates[j-1])continue;
arr.add(candidates[j]);
getList(list,arr,candidates,cur+candidates[j],j+1,target);
arr.remove(arr.size()-1);
}
}
}

下面是discuss上的解法,虽然一样,但是比我的要简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> combinationSum2(int[] cand, int target) {
Arrays.sort(cand);
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
dfs_com(cand, 0, target, path, res);
return res;
}
void dfs_com(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList(path));
return ;
}
if (target < 0) return;
for (int i = cur; i < cand.length; i++){
if (i > cur && cand[i] == cand[i-1]) continue;
path.add(path.size(), cand[i]);
dfs_com(cand, i+1, target - cand[i], path, res);
path.remove(path.size()-1);
}
}
如果觉得有帮助,给我打赏吧!