leetcode 39. Combination Sum和40. Combination Sum II

目录

39. Combination Sum

40. Combination Sum II

不使用used数组去重：

使用used数组去重：

---

39. Combination Sum

class Solution {vector<vector<int>> res;vector<int> com;int sum = 0;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(0,candidates,target);return res;}void backtracking(int start,vector<int>& candidates, int target){if(sum >= target){if(sum == target)res.push_back(com);return;}for(int i = start;i < candidates.size();i++){if(sum + candidates[i] > target)continue;com.push_back(candidates[i]);sum += candidates[i];backtracking(i,candidates,target);//candidates[i]可以重复使用，所以这里的start要传入icom.pop_back();sum -= candidates[i];}}
};

40. Combination Sum II

本题关键是去重。

不使用used数组去重：

去重条件是

 if(i > start && candidates[i] == candidates[i-1])//本题的关键，树层去重continue;

class Solution {vector<vector<int>> res;vector<int> com;int sum = 0;
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());//后面去重是需要先对candidates排序backtracking(candidates,target,0);return res;}void backtracking(vector<int>& candidates,int target,int start){if(sum >= target){if(sum == target)res.push_back(com);return;}for(int i = start;i < candidates.size();i++){if(i > start && candidates[i] == candidates[i-1])//本题的关键，树层去重continue;if(sum + candidates[i] > target)continue;com.push_back(candidates[i]);sum += candidates[i];backtracking(candidates,target,i+1);com.pop_back();sum -= candidates[i];}}
};

使用used数组去重：

去重条件是：

            if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)//本题的关键，树层去重continue;

class Solution {vector<vector<int>> res;vector<int> com;int sum = 0;vector<bool> used;
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());//后面去重是需要先对candidates排序used.resize(candidates.size(),false);backtracking(candidates,target,0);return res;}void backtracking(vector<int>& candidates,int target,int start){if(sum >= target){if(sum == target)res.push_back(com);return;}for(int i = start;i < candidates.size();i++){// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)//本题的关键，树层去重continue;if(sum + candidates[i] > target)continue;com.push_back(candidates[i]);sum += candidates[i];used[i] = true;backtracking(candidates,target,i+1);com.pop_back();sum -= candidates[i];used[i] = false;}}
};