组合总和

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

示例 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
输出: []

这题和上一题很像，但是要注意的是，这题是可以重复选的，所以要注意的是，枚举选哪个的时候，要从 $i$ 开始枚举，而不是从 $i+1$ 开始枚举。以及选或不选的情况，也要递归到处理 $i$而不是 $i+1$。

C++

class Solution {
public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> temp;
    int n =candidates.size();
    function<void(int,int)> dfs =[&](int i,int k){

    if(k==target){
      res.push_back(temp);
      return ;
    }
    if(i==n || k >target){
      return;
    }
    //选或不选

    //不选
    dfs(i+1,k);

    //选
    k += candidates[i];
    temp.push_back(candidates[i]);
    dfs(i,k);//因为可以重复选
    k -= candidates[i];
    temp.pop_back();
    };
    dfs(0,0);
    return res;
  }
};

C++

class Solution {
public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    vector<int> path;
    function<void(int, int)> dfs = [&](int i, int left) {
      if (i == candidates.size()) {
        return;
      }
      if (left == 0) {
        // 找到一个合法组合
        ans.push_back(path);
        return;
      }
      if (left < candidates[i]) {
        return;
      }
      // 枚举选哪个
      for (int j = i; j < candidates.size(); j++) {
        path.push_back(candidates[j]);
        dfs(j, left - candidates[j]);
        path.pop_back(); // 恢复现场
      }
    };
    dfs(0, target);
    return ans;
  }
};

更新日志

2024/12/15 12:44

查看所有更新日志

• 64700-update leetcode于 2024/12/15