leetcode题库39.组合总和——递归穷举

Aneverforget / 2023-09-03 / 原文

class Solution:
    def combinationSum(self, candidates, target):
        res,ans=[],[]
        def findpath(candidates):
            if sum(ans)==target:
                res.append(ans.copy())
                return
            if sum(ans)>target:
                return
            for k,i in enumerate(candidates):                
                for repeat in range(1,target+1):
                    for _ in range(repeat):
                        ans.append(i)
                    print(i)
                    findpath(candidates[k+1:])
                    for _ in range(repeat):
                        ans.pop()
            return
        findpath(candidates)
        return res

try:
    solution=Solution()
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    res=solution.combinationSum([7,2,1],7)
    print(res)
except:
    print('error')

　　在评论区看到高分题解：

from typing import List


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

        def dfs(candidates, begin, size, path, res, target):
            if target == 0:
                res.append(path)
                return

            for index in range(begin, size):
                residue = target - candidates[index]
                if residue < 0:
                    break

                dfs(candidates, index, size, path + [candidates[index]], res, residue)

        size = len(candidates)
        if size == 0:
            return []
        candidates.sort()
        path = []
        res = []
        dfs(candidates, 0, size, path, res, target)
        return res