【LetMeFly】39.组合总和：回溯 + 剪枝

力扣题目链接：https://leetcode.cn/problems/combination-sum/

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

 

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

 

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

解题方法：回溯 + 剪枝

写一个函数dfs(target, index)，用来处理距离目标还剩target，处理过候选数组的[0, index)的情况。

为了实现这个函数，我们还需要两个“全局”变量（或者通过参数传递）：ans用来存放所有可行的情况（答案）、now用来存放当前已选元素。

函数dfs终止条件：

• target为0：now为一种可选方案，now加入ans数组并终止递归
• index超出候选数组的下标范围：递归终止

函数dfs要做的事：

1. 在已选方案now的基础上，不选当前元素candidates[index]：递归dfs(target, index + 1)
2. 在已选方案now的基础上，选择当前元素candidates[index]：将candidates[index]加入now数组，递归dfs(target - candidates[index], index)，（回溯）将candidates[index]从now数组中剔除

剪枝方案：target - candidates[index] >= 0时再递归回溯。

• 时间复杂度$O(Size(ans))$
• 空间复杂度$O(target)$：空间复杂度为递归深度，最坏情况下全是1要递归target次

AC代码

C++

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> now;

    void dfs(vector<int>& candidates, int target, int index) {
        if (!target) {
            ans.push_back(now);
            return;
        }
        if (index == candidates.size()) {
            return;
        }
        // not choose
        dfs(candidates, target, index + 1);
        // choose
        if (target - candidates[index] >= 0) {
            now.push_back(candidates[index]);
            dfs(candidates, target - candidates[index], index);  // 这里不能是index + 1，因为可以重复选择
            now.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def dfs(self, target: int, index: int) -> None:
        if not target:
            self.ans.append(self.now[:])
            return
        if index == len(self.candidates):
            return
        # not choose
        self.dfs(target, index + 1)
        # choose
        if target >= self.candidates[index]:
            self.now.append(self.candidates[index])
            self.dfs(target - self.candidates[index], index)
            self.now.pop()        

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.ans = []
        self.now = []
        self.candidates = candidates
        self.dfs(target, 0)
        return self.ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/137994260