组合总和

last modify

问题简述

给你一个 无重复元素 的整数数组 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

相关问题

Last updated