设置的begin其实就是放元素的位置！！！没声明candidates数组不重复，所以去重时参考全排列二，对于数组里的重复元素需要进行去重.相比于组数总和一这题需要两次去重，第一次是深度优先遍历里同一支不可以重复使用就是i+1. 第二次是因为有相同的元素，所以前面用过的再后面的分支里也不能再使用。注意使用了used数组之后还是需要begin因为顺序不一样的也算是重复。

class Solution(object):def combinationSum2(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""candidates.sort()res = []sol = []vsd = [0]*len(candidates)def backtrack(res, sol, vsd,begin, sum):if sum == target:res.append(sol[:])for i in range(begin, len(candidates)):if sum + candidates[i] > target:return if i > 0 and candidates[i] == candidates[i-1] and vsd[i-1] == 0:continuevsd[i] = 1sum += candidates[i]sol.append(candidates[i])backtrack(res, sol, vsd, i+1, sum)vsd[i] = 0sum -= candidates[i]sol.pop()backtrack(res, sol, vsd,0, 0)return res

也可以直接使用begin位置进行剪枝，因为重复一定发生在同一层（排序后）。可以这样做的原因是比如【1，1，2，5，6，7，10】。target = 8 。回溯相当于DFS。首先搜索第一个1的所有答案。 搜索完了再搜索第二个1。注意搜索第二个1 的时候所有答案肯定包含在了第一个1里面。所以剪枝。当第一个1搜索完了for循环里i应该等于begin+1 > begin

def combinationSum2(self, candidates, target):res = []sol = []candidates.sort()def backtrack(begin,target):if target == 0:res.append(sol[:])return for i in range(begin,len(candidates)):if target - candidates[i] < 0:return if i > begin and candidates[i] == candidates[i-1]:  #只有在程序返回的时候才会执行for循环的下一句，这时会出现i>begin的情况continue                                        #i>begin的意思是，同一层前面的深度层搜索完成了，返回到这一层尝试下一个数。这时如果两个数相同的话，说明当前这个数的答案已经找到过了。sol.append(candidates[i])backtrack(i+1, target-candidates[i])sol.pop()backtrack(0,target)return res