Combination Sum II
问题：给定一个无重复的数组candidates和一个目标值target，根据数组中的元素输出和为目标值的所有可能组合，数组中的每个元素不能多次使用，输出结果不能有重复的组合。数组中的数和target均为正数
示例：
输入：candidates = [1,2,3,5,6] target = 6
输出：[[1,2,3],[6]]
解决思路：对candidates进行排序，之后遍历，并相应的减小target，递归进行，直到target为0.
Python代码：
class Solution(object): def combinationSum2(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ self.out = [] candidates.sort() self.Sum(candidates,target) return self.out def Sum(self,candidates,target,res=[],use=[]): if not target: self.out.append(res) return for i in range(len(candidates)):
# Avoid duplicate usage of the same elements in cnadidates if i > 0 and candidates[i] == candidates[i-1]: continue can = candidates[i] if can <= target: # To avoid duplicate usage of elements and duplicate combinations, input "candidaters[i+1:] instead of candidates" self.Sum(candidates[i+1:],target-can,res+[can]) else: break