Leetcode_Combination Sum 回溯法
程序员文章站
2022-05-21 22:39:01
...
39. Combination Sum
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<vector<int>> res;
vector<int> temp;
backTrack(candidates,target,res,temp,0);
return res;
}
void backTrack(vector<int>& candidates,int target,vector<vector<int> >& res,vector<int> &temp,int begin)
{
if(target==0)
{
res.push_back(temp);
return;
}
for(int i=begin;i<candidates.size()&&candidates[i]<=target;i++)
{
temp.push_back(candidates[i]);
backTrack(candidates,target-candidates[i],res,temp,i);
temp.pop_back();
}
}
};
思路就是先排序,然后从小到大开始递归,递归的参数有:目标值(每次减去当前值)直到0,当前构造出来的数组,起始坐标等。
40. Combination Sum II
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<vector<int>> res;
vector<int> temp;
backTrack(candidates,target,res,temp,0);
return res;
}
void backTrack(vector<int>& candidates,int target,vector<vector<int>> &res,vector<int> &temp,int begin)
{
if(target<0)
return;
else if(target==0)
{
res.push_back(temp);
return;
}
for(int i=begin;i<candidates.size()&&candidates[i]<=target;i++)
{
if(i>begin&&candidates[i]==candidates[i-1])
continue;
temp.push_back(candidates[i]);
backTrack(candidates,target-candidates[i],res,temp,i+1);
temp.pop_back();
}
}
};
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> temp;
backTrack(k,n,res,temp,1);
return res;
}
void backTrack(int depth,int target,vector<vector<int>>&res,vector<int> &temp,int begin)
{
if(depth<0||target<0)
return;
else if(depth==0&&target==0)
{
res.push_back(temp);
return;
}
for(int i=begin;i<=9&&i<=target;i++)
{
temp.push_back(i);
backTrack(depth-1,target-i,res,temp,i+1);
temp.pop_back();
}
}
};
本题要递归的还有深度,因为题目要求三个数字相加,那么递归深度必须为3.