Leetcode 40. Combination Sum II (python+cpp)

题目

解析：

这题可以看作是39的follow up，区别在于1. 原数组有重复数字，因为有重复数字，就说明用39这样的方法可能会产生重复的结果，比如原数组[1,7,1]，target是8，那就可能出现[1,7]和[7,1]同时被认为是valid的结果。这个情况其实跟做permutation那一系列题目一样的。 2. 而且每个数字只能用一次，所以只需要在39的基础上修改这两个地方就可以了：

• 针对1，解决方法跟permutation类似，把原数组排序，然后每个recursion level建立一个visited数组避免重复结果
• 每个数字只能用一次那么recursion的时候传i + 1就阔以了
  python代码如下：

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:def back_tracking(curr,first):if sum(curr) == target:ans.append(curr[:])returnif sum(curr) > target:returnvisited = set()for i in range(first,len(candidates)):if candidates[i] in visited:continuecurr.append(candidates[i])back_tracking(curr,i+1)curr.pop()visited.add(candidates[i])ans = []candidates.sort()back_tracking([],0)return ans

C++代码如下：

class Solution {
    
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> ans;vector<int> curr;sort(candidates.begin(),candidates.end());back_tracking(0,curr,0,target,ans,candidates);return ans;}void back_tracking(int first,vector<int> curr,int currsum,int target,vector<vector<int>>& ans,vector<int>& candidates){
    if (currsum==target){
    ans.push_back(curr);return;}if (currsum>target) return;set<int> visited;for (int i=first;i<candidates.size();++i){
    if (visited.count(candidates[i])) continue;curr.push_back(candidates[i]);back_tracking(i+1,curr,currsum+candidates[i],target,ans,candidates);curr.pop_back();visited.insert(candidates[i]);}}
};