# 40. Combination Sum II """ given a collection of candidate numbers and a target number, find all unique combinations in 'candidates' where the candidate numbers sum to 'target'. each number in 'candidates' may only be used once """ class Solution(object): def dfs(self, candidates, target, idx, path, res): if target <= 0: if target == 0: res.append(path) return for i in range(idx, len(candidates)): if i > idx and candidates[i] == candidates[i - 1]: continue self.dfs( candidates, target - candidates[i], i + 1, path + [candidates[i]], res ) def combinationSum2(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ ans = [] self.dfs(sorted(candidates), target, 0, [], ans) return ans if __name__ == "__main__": obj = Solution() print(obj.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8)) print(obj.combinationSum2(candidates=[2, 5, 2, 1, 2], target=5))