HHot 100C++ 图解

39. 组合总和

一句话套路组合回溯,递归传 i 允许重复选

题目描述

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

思路

时间O(2^target/min)
空间O(target/min)

思路

组合型回溯 + 「同一个元素可重复选」-> 递归时传 i 而不是 i+1。

排序后可以在 sum > target 时直接 break(后续更大),这是最有价值的剪枝。

对比 Q40(每个元素只能用一次且含重复值):传 i+1,并加if (i > start && candidates[i] == candidates[i-1]) continue; 去重。

图解

2 0 3 1 6 2 7 3
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/10_backtracking.cpp27 行
namespace lc0039 {
class Solution {
 public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());  // 为了 break 剪枝
    vector<vector<int>> ans;
    vector<int> path;
    dfs(candidates, 0, target, 0, path, ans);
    return ans;
  }

 private:
  static void dfs(const vector<int>& c, int start, int target, int sum, vector<int>& path,
                  vector<vector<int>>& ans) {
    if (sum == target) {
      ans.push_back(path);
      return;
    }
    for (int i = start; i < (int)c.size(); ++i) {
      if (sum + c[i] > target) break;  // 已排序 -> 后面只会更大,整层剪掉
      path.push_back(c[i]);
      dfs(c, i, target, sum + c[i], path, ans);  // 注意是 i,不是 i+1
      path.pop_back();
    }
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q39_combination_sum7 行
lc0039::Solution s;
vector<int> a{2, 3, 6, 7};
CHECK_EQ(s.combinationSum(a, 7), vector<vector<int>>({{2, 2, 3}, {7}}));
vector<int> b{2, 3, 5};
CHECK_EQ(s.combinationSum(b, 8), vector<vector<int>>({{2, 2, 2, 2}, {2, 3, 3}, {3, 5}}));
vector<int> c{2};
CHECK_EQ(s.combinationSum(c, 1), vector<vector<int>>{});  // 凑不出来

↑↓ 选择↵ 打开/ 随时唤起