递归回溯也是经常用到的，最近重新看了两道，归纳一下吧。
对于此类的问题，关键点是找递归开始即回溯回来的点。例如：对于数组问题，典型的这个点可以是：(1)index是否到末尾了？(2)当前元素是否进行使用过了？
话不多说，看下面三类典型的
1.求子集和的问题
注意几道求子集和的问题的区别，解法大体都是类似的，用递归回溯的方法
39.Combination Sum
给定数组中的数字是没有重复的，但是每个数字可以使用多次。
因此在递归时用for(int i=pos;i<candidates[i].size();i++)后下一次递归
solve(candidates,result,temp,target-candidates[i],i)
40.Combination Sum II
给定数组中的数字可能出现重复，但是每个数字只能使用一次。
因此在递归时用for(int i=pos;i<candidates[i].size();i++)后下一次递归
solve(candidates,result,temp,target-candidates[i],i+1)但是此时需要添加一个set来判定是否已经取到过子集
216. Combination Sum III
此时给定的是子集中的元素个数k，目标n，也就是从1-9中找出k个数的和为n。
由于限定了子集的元素个数，因此每次递归的时候，除了在之前两道的target-i的基础上，同样需要k-1。
for(int i=pos;i<10;i++)
solve(k-1,n-i,i+1,result,temp);而判断递归返回的条件为当前使用的个数已经为k个了
377. Combination Sum IV
此时给定的数组中元素没有重复值，可以重复使用元素，并且不同的是：此时相同的元素不同的排列算作不同的顺序，返回最终的组合个数
考虑不加限定条件的递归，此时会出现时间限制，因此考虑用dp的思想来解决。对于i<target的某一点的组合数为
dp[i]=dp[i]+dp[i-nums[j]]其中nums[j]为给定数组中的各个元素
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> temp; //存的是当前递归的使用数组
sort(candidates.begin(),candidates.end()); //sort是必不可少的
solve(temp,candidates,target,0);
return res;
}
private:
vector<vector<int>> res;
void solve(vector<int>& temp,vector<int>& candidates,int target,int index){
if(!target){ //如果遍历到最后target为0，说明找到了符合的情况
res.push_back(temp);
return;
}
if(target>0){ //只有当target仍然>0才有继续找的必要，不然直接弹出即可
for(int i=index;i<candidates.size();++i){
temp.push_back(candidates[i]);
solve(temp,candidates,target-candidates[i],i);
temp.pop_back();
}
}
}
};
class Solution {
public:
set<vector<int>> S;
vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<int> item;
solve(candidates,target,item,0);
return res;
}
private:
void solve(vector<int>& candidates,int target,vector<int>& item,int pos){
if(target==0){
if(S.find(item)==S.end()){
S.insert(item);
res.push_back(item);
}
return;
}
if(target>0){
for(int i=pos;i<candidates.size();i++){
item.push_back(candidates[i]);
solve(candidates,target-candidates[i],item,i+1);
item.pop_back();
}
}
}
}; Leetcode216. Combination Sum III
//跟之前第一道应该一样，candidates为1-9，target为n，现在多了一个限定条件k个数
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> nums;
for(int i=1;i<=9;++i)
nums.push_back(i);
vector<int> temp;
solve(k,n,nums,temp,0,0);
return res;
}
private:
vector<vector<int>> res;
void solve(int k,int n,vector<int>& nums,vector<int>& temp,int cnt,int index){
if(!n){
if(cnt==k)
res.push_back(temp);
return;
}
for(int i=index;i<nums.size();++i){
temp.push_back(nums[i]);
solve(k,n-nums[i],nums,temp,cnt+1,i+1);
temp.pop_back();
}
}
}; Leetcode 377. Combination Sum IV
有点坑啊，之前就像前面分析的DP方法，直接一步到位，后来不知道谁改了样例，死活过不了，改成unsigned long可行
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
// dp[k] : all possible combinations sum to k
vector<unsigned long> dp(target + 1, 0);
dp[0] = 1; // subset with nothing
for (int i = 0; i < nums.size() && nums[i] <= target; ++i)
dp[nums[i]] = 1;
for (int i = 1; i <= target; ++i)
{
for (int j : nums)
if (j < i)
dp[i] += dp[i-j];
else
break;
}
return dp[target];
}
}; 2. 数据元素的组合
这两题同样是用回溯法，现在想找数组元素的所有可能组合。这个和前面的combination sum非常的像，只不过那一题中我们用的是pos参数，如果遍历到达了数组末端，那么停止返回；
1.而在46这道题中，我们需要用一个辅助vec来标记当前元素是否进行使用过了，如果使用过了，那么我们应该直接跳过进行下一个元素的判断，此时递归结束的条件是item数组的大小已经和nums一样了（也即是所有元素都已经使用了）
2.那么在47题中，就像combination sumii中需要考虑重复元素了，那么这里也是一样的，原本的数组中是包含有重复元素的，那么同样的，我们用set来保证唯一性。
3.77和46基本一模一样
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> item;
vector<bool> status(nums.size(),false);
backtracking(nums,item,status);
return res;
}
private:
void backtracking(vector<int>& nums,vector<int>& item,vector<bool>& status){
if(item.size()==nums.size()){ //此时因为不用pos参数，所以递归返回条件是数组大小相等
res.push_back(item);
return;
}
for(int i=0;i<nums.size();i++){
if(!status[i]){ //如果当前元素没有被用过，那么我们可以进行使用，并进行递归
item.push_back(nums[i]);
status[i]=true;
backtracking(nums,item,status);
item.pop_back();
status[i]=false;
}
}
}
}; 多使用一个set来限定唯一性（因为含有重复元素）
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> temp;
vector<bool> visit(nums.size(),false);
dfs(nums,temp,visit);
return res;
}
private:
vector<vector<int>> res;
set<vector<int>> S;
void dfs(vector<int>& nums,vector<int>& temp,vector<bool>& visit){
if(nums.size()==temp.size()){ //set保证唯一性，其他都一样
if(!S.count(temp)){
res.push_back(temp);
S.insert(temp);
}
return;
}
for(int i=0;i<nums.size();++i){
if(!visit[i]){ //当前项未进行过访问
visit[i]=true;
temp.push_back(nums[i]);
dfs(nums,temp,visit);
temp.pop_back();
visit[i]=false;
}
}
}
};
}; 跟46几乎一样
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<int> vec;
vector<int> temp;
for(int i=1;i<=n;++i)
vec.push_back(i);
int cnt=0;
dfs(vec,temp,k,0,0);
return res;
}
private:
vector<vector<int>> res;
void dfs(vector<int>& vec,vector<int>& temp,int k,int cnt,int pos){
if(cnt==k){
res.push_back(temp);
return;
}
for(int i=pos;i<vec.size();++i){
temp.push_back(vec[i]);
dfs(vec,temp,k,cnt+1,i+1);
temp.pop_back();
}
}
}; 3. 求子集的问题
就看两题把，subset I和subset II，两者不同的地方是给定的数组中是否有重复元素，那么就像我们之前碰到过的，如果有重复元素的情况，多用一个set来限定唯一性就解决了。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> temp;
res.push_back(temp); //空集不要漏掉
dfs(nums,temp,0);
return res;
}
private:
vector<vector<int>> res;
void dfs(vector<int>& nums,vector<int>& temp,int pos){
if(pos>=nums.size()) //到末尾了进行返回
return;
for(int i=pos;i<nums.size();++i){
temp.push_back(nums[i]);
res.push_back(temp);
dfs(nums,temp,i+1);
temp.pop_back();
}
}
};
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end()); //sort保证排列
vector<int> vec;
res.push_back(vec); //空集先进
dfs(nums,vec,0);
return res;
}
private:
vector<vector<int>> res;
set<vector<int>> S;
void dfs(vector<int>& nums,vector<int>& vec,int pos){
if(pos>=nums.size())
return;
for(int i=pos;i<nums.size();++i){
vec.push_back(nums[i]);
if(!S.count(vec)){
res.push_back(vec);
S.insert(vec);
dfs(nums,vec,i+1);
}
vec.pop_back();
}
}
};
京公网安备 11010502036488号