组合总和

标签: 数组 回溯

难度: Medium

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

注意：本题与主站 39 题相同： https://leetcode-cn.com/problems/combination-sum/

Submission

运行时间: 27 ms

内存: 16.1 MB

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        n = len(candidates)
        candidates.sort()
        path = []
        def recur(start,candidates, target):
            for i in range(start, len(candidates)):
                if candidates[i] <= target:
                    path.append(candidates[i])
                    if candidates[i] == target: 
                        ans.append(path.copy())
                    recur(i, candidates, target-candidates[i])
                    path.pop()
                else:
                    return
        recur(0, candidates, target)
        return ans

Explain

该题解采用了回溯算法，首先对输入数组进行排序以便优化搜索过程。定义一个辅助函数 recur，递归地尝试每一个可能的数字组合。从当前位置开始，尝试每个数字，如果当前数字小于等于目标值 target，则将其加入到当前路径（path）中，并递归地调用 recur，此时目标值减少当前数字的值。如果当前数字等于目标值，则将当前路径添加到答案列表中。每次递归返回后，撤销上一个选择（回溯）。如果当前数字大于目标值，则终止当前分支的搜索。

时间复杂度: O(n^target/min(candidates))

空间复杂度: O(target / min(candidates))

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = [] # 结果列表
        n = len(candidates) # 候选数字的数量
        candidates.sort() # 对候选数组进行排序
        path = [] # 当前路径，用于记录当前的组合
        def recur(start, candidates, target):
            for i in range(start, len(candidates)):
                if candidates[i] <= target: # 当前数字小于等于目标值时继续处理
                    path.append(candidates[i]) # 选择当前数字
                    if candidates[i] == target: # 找到一个有效的组合
                        ans.append(path.copy()) # 将当前路径复制到结果列表中
                    recur(i, candidates, target - candidates[i]) # 继续递归，目标值减少
                    path.pop() # 回溯，撤销选择
                else: # 当前数字大于目标值，不再继续搜索
                    return
        recur(0, candidates, target)
        return ans

Explore

在题解中，对候选数组进行排序主要是为了优化搜索过程。排序后，当遇到一个数字大于当前目标值时，可以立即终止循环，避免继续探索更大的数，从而减少不必要的递归调用。这种剪枝策略有助于减少搜索空间，提高算法效率。

虽然理论上可以通过迭代来实现回溯算法，通常使用栈来模拟递归过程，但递归形式的回溯在理解和实现上更为直观和简洁。迭代版本可能在空间利用上有优势，因为可以更精细地控制栈的使用，但编码复杂度较高，可读性和可维护性可能下降。通常，递归和迭代的效率差别不大，主要取决于具体实现和问题规模。

这种剪枝策略是基于问题的特性：如果当前数字已经大于目标值，那么在这个数字或更大的数字上继续搜索只会得到更大的数，而不可能得到等于目标值的解。因此，这种策略不会漏掉任何正确的解，是一种有效的优化方法。