组合总和

问题简述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target，
找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合，
并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取。
如果至少一个数字的被选数量不同，则两种组合是不同的。

思路：递归回溯

Python：写法1（标准写法，推荐）

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        ret = []

        def dfs(s, start, tmp):
            if s >= target:
                if s == target:
                    ret.append(tmp[:])
                return

            for i in range(start, len(candidates)):
                c = candidates[i]
                tmp.append(c)
                dfs(s + c, i, tmp)  
                # 这里传入 i 表示从 candidates 第 i 个开始取，因此可以重复
                # 组合总和II 中不能重复取，相应的要传入 i+1
                tmp.pop()

        dfs(0, 0, [])
        return ret

Python：写法2（好记）

• 本写法不保证在其他相关问题上适用；

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        ret = []

        def dfs(s, tmp):
            if s >= target:
                if s == target:
                    ret.append(tmp[:])
                return
            
            for c in candidates:
                if tmp and c < tmp[-1]:  # 保证 tmp 内部有序来达到去重的目的
                    continue
                tmp.append(c)
                dfs(s + c, tmp)
                tmp.pop()
        
        dfs(0, [])
        return ret

相关问题

• 40. 组合总和 II - 力扣（LeetCode）