leetcode：39. 组合总和

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

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

解答 & 代码

解法一：递归回溯（朴素，无剪枝）

  1. class Solution {
  2. private:
  3.     vector<vector<int>> resultList;
  4.     vector<int> curCombine;
  6.     void dfs(vector<int> candidates, int start, int target)
  7.     {
  8.         // 递归结束条件 1：找到目标和，存入结果数组
  9.         if(target == 0)
  10.         {
  11.             resultList.push_back(curCombine);
  12.             return;
  13.         }
  14.         // 递归结束条件 2：超过目标和 or 已遍历完 candidates 数组
  15.         if(target < 0 || start >= candidates.size())
  16.             return;
  18.         // 回溯算法框架
  19.         for(int i = start; i < candidates.size(); ++i)
  20.         {
  21.             // 1. 选择 candidatas
  22.             curCombine.push_back(candidates[i]);
  23.             // 2. 递归遍历下一次回溯树: 注意这里 start 仍取 i，因为元素可以多次重复使用！
  24.             dfs(candidates, i, target - candidates[i]);
  25.             // 3. 撤销选择 canditates[i]
  26.             curCombine.pop_back();
  27.         }
  28.     }
  29. public:
  30.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  31.         dfs(candidates, 0, target);
  32.         return resultList;
  33.     }
  34. };

复杂度分析：

  • 时间复杂度 O()：
  • 空间复杂度 O(target)：取决于递归深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：44 ms, 在所有 C++ 提交中击败了 12.97% 的用户
  4. 内存消耗：36.9 MB, 在所有 C++ 提交中击败了 7.99% 的用户

解法二：递归回溯 + 剪枝

先对数组按从小到大排好序，那么每次递归调用 dfs(vector<int> candidates, int start, int target) 时，start 就是当前可取的最小元素，如果 target < candidates[start]，直接返回，这相当于一种剪枝操作

  1. class Solution {
  2. private:
  3.     vector<vector<int>> resultList;
  4.     vector<int> curCombine;
  6.     void dfs(vector<int> candidates, int start, int target)
  7.     {
  8.         if(target == 0)
  9.         {
  10.             resultList.push_back(curCombine);
  11.             return;
  12.         }
  13.         // 因为数组已升序排序，start 就是当前可取的最小元素，
  14.         // 如果 target < candidates[start]，直接返回
  15.         if(target < candidates[start] || start >= candidates.size())
  16.             return;
  18.         // 因为数组已升序排序，若遍历到 candidates[i] > target，也不再往后遍历
  19.         for(int i = start; i < candidates.size() && candidates[i] <= target; ++i)
  20.         {
  21.             curCombine.push_back(candidates[i]);
  22.             dfs(candidates, i, target - candidates[i]);
  23.             curCombine.pop_back();
  24.         }
  25.     }
  26. public:
  27.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  29.         sort(candidates.begin(), candidates.end());
  30.         dfs(candidates, 0, target);
  31.         return resultList;
  32.     }
  33. };

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 28.50% 的用户
  4. 内存消耗：14.1 MB, 在所有 C++ 提交中击败了 32.60% 的用户