39. 组合总和

Difficulty
Medium
Tags
回溯
URL
https://leetcode-cn.com/problems/combination-sum/
Star
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
示例 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]]
示例 3：
输入:candidates =[2],target = 1
输出:[]
示例 4：
输入:candidates =[1],target =1输出:[[1]]
示例 5：
输入:candidates =[1],target =2输出:[[1,1]]
提示：
  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500
通过次数321,301提交次数441,990

法1 回溯

思路
同组合类似，只不过上一题是找个数为k的组合，本题是找和为target的组和。
本题目对于同一元素可以取无限个，所以不能对和进行剪枝
题解
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        self.backtrack(path=[], sum_=0, target=target, candidates=candidates, start=0)
        return self.res

    def backtrack(self, path, sum_, target, candidates, start):
        if sum_ == target:
            self.res.append(path[:])
            return
        elif sum_ > target:
            return
        
        for i in range(start, len(candidates)):
            sum_ += candidates[i]
            path.append(candidates[i])
            self.backtrack(path, sum_, target, candidates, i)
            sum_ -= candidates[i]
            path.pop()