题目描述

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

candidates 中的数字可以无限制重复被选取。

说明：

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

来源，leetcode 每日一题 39. 组合总和

例如：ull,null,15,7],

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

解题思路

  1. 递归: 每次对 target-candidates[i]做递归

  2. 去除重复的组合

    代码

    1. class Solution {
    2. public:
    3.  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    4.  sort(candidates.begin(),candidates.end());
    5.  int len = candidates.size();
    6.  vector<int> path;
    7.  vector<vector<int>> ans;
    8.  dfs(candidates,target,0,len,path,ans);
    10.  return ans;
    11.  }
    13.  void dfs(vector<int> &candidates,int target,int begin,int len,vector<int> &path,vector<vector<int>> &ans){
    14.      if(target==0){
    15.         ans.push_back(path);
    16.         return;
    17.      }
    19.      if(target-candidates[begin]<0){
    20.         return;
    21.      }
    22.      for(int i=begin;i<len;i++){
    23.          path.push_back(candidates[i]);
    24.          dfs(candidates,target-candidates[i],i,len,path,ans);
    25.          path.pop_back();
    26.      }
    27.  } 
    28. };

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

说明：

  1. 所有数字（包括目标数）都是正整数。
  2. 解集不能包含重复的组合。

leetcode每日一题 40. 组合总和 Ⅱ

此题与上题相似，解法一致，不在赘述。

注意点

提高运行时间的一个办法，就是将函数里面的参数变成地址传递，而不是使用值传递。使用值传递，会使用赋值构造函数进行，这个过程是慢的。

代码

  1. class Solution {
  2. public:
  3.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  4.         sort(candidates.begin(), candidates.end());
  5.         map<vector<int>, int> answer;
  6.         vector<vector<int>> result;
  7.         vector<int> path;
  8.         dfs(answer, candidates, target, path, 0, candidates.size());
  9.         for (map<vector<int>, int>:: iterator it = answer.begin(); it != answer.end(); it++) {
  10.             result.push_back(it->first);
  11.         }
  12.         return result;
  13.     }
  14.     void dfs(map<vector<int>, int> & answer, vector<int>& candidates, int target, vector<int>& path, int begin, int len) {
  15.         if (begin >= len) {
  16.             return;
  17.         }
  18.         for (int i = begin; i < len; i++) {
  19.             if (candidates[i] > target) {
  20.                 return;
  21.             }
  22.             path.push_back(candidates[i]);
  23.             if (target == candidates[i]) {
  24.                 answer[path] += 1;
  25.                 path.pop_back();
  26.                 return;
  27.             }
  28.             dfs(answer, candidates, target-candidates[i], path, i + 1, len);
  29.             path.pop_back();
  30.         }
  32.     }
  33. };