leetcode 链接：组合总和

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解答 & 代码

dfs 搜索回溯
定义函数 void calCombinations(vector<int>& candidates, int target, int left, vector<int>& result, vector<vector<int>>& resultList) ，其中 candidates 是候选元素数组，target 是当前剩余的目标值，left 表示当前可以遍历 candidates 的左边界（为了避免得到重复解），result 是当前的组合（解），resultList 是解集

递归终止条件：target 比当前可以取的最小元素要小，不存在这样的解，直接返回
- 调用本递归函数之前，先对数组按从小到大排好序了，那么 left 就是当前可取的最小元素，这相当于一种剪枝操作
遍历可以访问的每个元素
- 该元素可以取：将该元素压入 result，
  - 如果该元素和 target 值相同，说明当前 result 就是一个解，存入 resultList
  - 否则，递归执行 calCombinations(candidates, target - candidates[i], i, result, resultList);
- 也可以不取该元素直接跳过：需要将该元素弹出 result，恢复原状，即回溯
时间复杂度：O(S)，其中 S 为所有可行解的长度之和

空间复杂度：O(target)，最坏情况下，需要递归 O(target) 层

class Solution {
private:
  void calCombinations(vector<int>& candidates, int target, int left, vector<int>& result, vector<vector<int>>& resultList)
  {
      // 递归结束条件：target 比当前可以取的最小元素要小，不存在这样的解，直接返回
      // 数组是从小到大排序的，left 代表当前可以访问的左边界（为了避免重复解，设立左边界）
      // 因此 candidates[left] 是当前可取的最小元素
      if(target < candidates[left])
          return;

      // 遍历所有可以访问的元素（如果元素大于 target，停止遍历）
      for(int i = left; i < candidates.size() && candidates[i] <= target; ++i)
      {
          // 在 result 末尾压入当前元素
          result.push_back(candidates[i]);
          // 如果存入当前元素后，target 变为 0 了，说明当前 result 是一个解，存入 reusltList
          if(target == candidates[i])
              resultList.push_back(result);
          // 否则，递归得到选取当前元素之后的解
          else
              calCombinations(candidates, target - candidates[i], i, result, resultList);

          // 回溯，从 result 末尾弹出当前元素，恢复原状，准备遍历下一个元素
          result.pop_back();
      }
  }
public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
      vector<int> result;
      vector<vector<int>> resultList;
      if(candidates.size() == 0)
          return resultList;

      sort(candidates.begin(), candidates.end());    // 先从小到大排序
      calCombinations(candidates, target, 0, result, resultList);
      return resultList;
  }
};

执行结果： ``` 执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 75.95% 的用户内存消耗：10.6 MB, 在所有 C++ 提交中击败了 80.23% 的用户 ```

CodeTop 企业题库

[中等] 39. 组合总和

题目

解答 & 代码