题目描述

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

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

思路解析

回溯，满足和，则加入res，否则，继续回溯更新

class Solution:
    def combinationSum(self, candidates, target):
        if not candidates or len(candidates) == 0:
            return
        candidates.sort()
        res = []
        def helper(temp, temp_sum, i):
            '''

            :param temp: 当前数组
            :param temp_sum: 当前组合的和
            :param i: 当前索引的位置
            :return:
            '''
            # 不符合要求，退出
            if temp_sum > target or i >= len(candidates):
                return
            # 满足条件
            if temp_sum == target:
                res.append(temp)
                return
            # 要还是不要
            helper(temp + [candidates[i]], temp_sum + candidates[i], i)
            helper(temp, temp_sum, i+1)
        helper([], 0, 0)
        return res

AC39

改动：就是如果一直满足一直要，否则才不要，选下一个

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i, tmp_sum, tmp):
            if  tmp_sum > target or i == n:
                return 
            if tmp_sum == target:
                res.append(tmp)
                return 
            for j in range(i, n):
                if tmp_sum + candidates[j] > target:
                    break
                backtrack(j,tmp_sum + candidates[j],tmp+[candidates[j]])
        backtrack(0, 0, [])
        return res

Ac39