39_组合总和

类型：数组

组合总和 💛

https://leetcode-cn.com/problems/combination-sum/

❓ 从无重复元素的数组 candidates 中找出所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

💡 回溯

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        track = []
        ans = []

        def trackback(start):
            if sum(track) == target:
                ans.append(track[:])
                return
            if sum(track) > target:
                return
            if start >= n:
                return

            for i in range(start, n):
                track.append(candidates[i])
                trackback(i)
                track.pop()

        trackback(0)
        return ans

时间复杂度：O(S)，其中 S 为所有可行解的长度之和。

空间复杂度：O(target)。空间复杂度取决于递归的栈深度，在最差情况下需要递归 target 层。