题目

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

candidates 中的每个数字在每个组合中只能使用一次。

说明
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例

示例 1
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

解答

方案1：回溯法

我们写一个函数helper，用来实现回溯操作。

输入参数

1. 当前要考察的元素所在的下标（index）；
2. 加到当前为止的和（cur_sum）；
3. 临时列表（cur_list），用来记录组成当前和cur_sum所使用过的所有加数；

操作流程

1. 判断操作是否合法，用来限制操作次数，有两个判断条件：
   （1）当前考察的元素所在下标i是否合法，是否出现越界；
   （2）当前为止的和cur_sum是否已经超过目标值target，如果已经超过，则没有必要再进行操作。
2. 判断是否已经满足条件，即cur_sum是否已经等于目标值target，如果已经相等，则把组成cur_sum的各个加数cur_list加入到结果列表res中。
3. 考察在当前和中加入index之后的每个元素candidates[index]的情况，即：helper(i+1, cur_sum+candidates[index], cur_list+[candidates[index]])，i从index到最后一个元素。

注，这里可以不使用排序，因为数组中的元素是没有重复的。

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :param candidates: List[int]
        :param target: int
        :return: List[List[int]]
        """
        def helper(index, cur_sum, cur_list):
            """
            :param index: 当前考察的元素
            :param cur_sum: 当前和
            :param cur_list: 获得cur_sum所用的元素
            :return:
            """
            # 跳出递归的条件
            if cur_sum > target or index > len(candidates):
                return

            # 如果找到符合条件的子数组，则添加到结果中
            if cur_sum == target and cur_list not in res:
                res.append(cur_list)
                return

            # 考虑分别把之后的每一个元素加入结果中
            for i in range(index, len(nums)):
                helper(i + 1, cur_sum + nums[i], cur_list + [nums[i]])
        
        # 排序，有必要
        nums = sorted(candidates)
        res = []
        helper(0, 0, [])
        return res

如有疑问或建议，欢迎评论区留言~