40. Combination Sum II

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

Each number in candidates 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.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

注意需要排序

 1 class Solution {
 2     private List<List<Integer>> res = new ArrayList<>();
 3     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 4         List<Integer> temp = new ArrayList<Integer>();
 5         Arrays.sort(candidates);
 6         help(temp,candidates,0,0,target);
 7         return res;
 8     }
 9     private void help(List<Integer> temp,int[] nums,int index,int cursum,int target){
10         if(cursum>target)
11             return;
12         else if(cursum==target)
13             res.add(new ArrayList<Integer>(temp));
14         else{
15             for(int i = index;i<nums.length;i++){
16                 if(i > index && nums[i] == nums[i-1]) continue; // skip duplicates
17                 temp.add(nums[i]);
18                 help(temp,nums,i+1,cursum+nums[i],target);
19                 temp.remove(temp.size()-1);
20             }
21         }
22     }
23 }

 1 class Solution:
 2     def __init__(self):
 3         self.res = []
 4     def combinationSum2(self, candidates, target):
 5         """
 6         :type candidates: List[int]
 7         :type target: int
 8         :rtype: List[List[int]]
 9         """
10         def help(x,temp,index,cursum,t):
11             temp = temp[:]
12             if cursum>t:
13                 return
14             if(cursum==t):
15                 self.res.append(temp)
16             for i in range(index,len(x)):
17                 if(i > index and x[i]==x[i-1]):
18                     continue
19                 temp.append(x[i])
20                 help(x,temp,i+1,cursum +x[i],t)
21                 temp.pop(-1)
22                 
23                 
24         x = sorted(candidates)
25         help(x,[],0,0,target)
26         return self.res
27 
28

与上一个题目不同，这个题要求每个数字只能用一次，

所以需要从i+1开始搜索（代码18行）

candidates 中可能会有重复的元素

[10,1,2,7,6,1,5]
8

如果没有19行，结果为

Your answer

[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]

Expected answer

[[1,2,5],[1,7],[1,1,6],[2,6]]


因为 1,1,2,5,6,7,10

第一个1会生成结果125,17
第二个1也会生成125,17

2019.3.12

 1 class Solution {
 2 public:
 3     vector<vector<int>> finalres ;
 4     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
 5         if(candidates.size()==0) return finalres;
 6         sort(candidates.begin(),candidates.end());
 7         vector<int> curres;
 8         help(0,curres,candidates,0,target);
 9         return finalres;
10         
11     }
12     void help(int cursum,vector<int>& curres,vector<int>& candidates,int index,int target){
13         if(cursum==target)
14             finalres.push_back(curres);
15         if(cursum>target)
16             return;
17         for(int i = index;i<candidates.size();i++){
18             if(i >index && candidates[i]==candidates[i-1]) continue;
19             curres.push_back(candidates[i]);
20             help(cursum,curres,candidates,i+1,target-candidates[i]);
21             curres.pop_back();
22 
23         }
24     }
25 };