leetcode [39] 组合总和

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

dfs回溯，终止条件是当前值等于目标值，或者加上候选值后大于目标值。如果没有终止，将当前值加入序列，继续dfs。注意，由于不让重复，所以加入一个位置坐标表示后续的起始位置。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        def dfs(seq, cur, pos):
            nonlocal candidates, target, ans
            if cur == target:
                ans.append(seq)
            for i in range(pos, len(candidates)):
                if cur + candidates[i] > target:
                    break
                dfs(seq + [candidates[i]], cur + candidates[i], i)
        dfs([], 0, 0)
        return ans