[数据结构与算法]LeetCode第40题：组合总和 II

题目：

思路：
对于“寻找”这种题目，可以用递归的方法去做，首先把数组排序，然后让target分别减去数组中的每一个数，如果减到最后的结果不为0，则返回上一级，重新选个数进行减法运算，把结果等于0的存储，不等于0的扔掉。整个逻辑写完可以用“树”来表示（此处图有时间补上，有图就很好理解）

代码如下：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        # res设为最终结果
        res = []
        length = len(candidates)
        # path设为临时存储
        path = []
        if candidates == "":
            return res

        # 创建递归方法，每次减去一个数，直到target - candidates[i] == 0
        def dfs(candidates, begin, length, path, res, target):
            if target < 0:
                return 0
            if target == 0:
                res.append(path)
                return 0
            for i in range(begin, length):
                if i != begin and candidates[i] == candidates[i - 1]:  # 保证每个数字只使用一次
                    continue
                dfs(candidates, i+1, length, path + [candidates[i]], res, target - candidates[i])

        dfs(candidates, 0, length, path, res, target)
        return res