LeetCode-40-组合总和 II

原题链接：https://leetcode-cn.com/problems/combination-sum-ii/

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

image.png

解题思路：

1. 思路同：https://leetcode-cn.com/problems/combination-sum/；
2. 不同点在于需要区分重复的情况，加了条判断if i > start and candidates[i - 1] == candidates[i]: continue，即第一轮遍历到第二个1时，因为前一个值为1，跳过该轮次，即避免了[1,2,5]重复出现的情况。

Python3代码：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def func(start, track, target):
            for i in range(start, len(candidates)):
                if candidates[i] == target:
                    track.append(candidates[i])
                    res.append(track)
                    return 
                if i > start and candidates[i - 1] == candidates[i]:
                    continue
                if candidates[i] < target:
                    func(i+1, track+[candidates[i]], target-candidates[i])
                if candidates[i] > target:
                    return 
        func(0, [], target)
        return res