递归搜索与回溯专题篇一

目录

组合

目标和

组合总和

字母大小全排列

---

组合

题目

思路

解决这道题利用DFS，决策树是怎样的？以n=4，k=3为例：

因为每个数只用到一次，因此需要剪枝，将出现重复数字的枝剪掉，因为组合中元素的先后顺序没有影响，因此需要将小于对应位置值的值剪掉，即从该位置的值后面的值进行DFS。

代码

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> combine(int n, int k) {dfs(n,k,1);return ret;}void dfs(int n,int k,int pos){if(path.size()==k){ret.push_back(path);return;}for(int i=pos;i<=n;i++){path.push_back(i);dfs(n,k,i+1);path.pop_back();}}
};

目标和

题目

思路

这道题无非是给每个位置添加上‘+’或‘-’号，针对每个位置的值，无非是两种情况，添加‘+’或‘-’号，因此针对每个位置的两种情况进行DFS，当处理完最后一个位置的数后，判断得到的值是否等于target，如果等于，就对次数进行++.

代码

class Solution {int ret,aim;public:int findTargetSumWays(vector<int>& nums, int target) {aim=target;dfs(nums,0,0);return ret;}void dfs(vector<int>& nums,int pos,int path){if(pos==nums.size()){if(path==aim)ret++;return;}dfs(nums,pos+1,path+nums[pos]);dfs(nums,pos+1,path-nums[pos]);}
};

组合总和

题目

思路

解决这道题将采用两种解法，但是两种解法都是利用DFS。

解法一

分析每个位置放什么数，因为题目中说明无重复元素且同一个元素可以无限制重复被选取，因此对每个位置进行DFS时，递归的位置可以依旧是原来的位置的值，递归出口是：总和等于target，或者总和大于target，或者递归位置大于数组的最后一个元素的位置。

代码

 class Solution {public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates,target,0,0);return vv;}void dfs(vector<int>& candidates, int target,int pos,int sum){if(sum==target){vv.push_back(v);return;}if(sum>target || pos==candidates.size()) return;//分析每个位置放什么数for(int i=pos;i<candidates.size();i++){v.push_back(candidates[i]);dfs(candidates,target,i,sum+candidates[i]);v.pop_back();}}};

解法二

分析每个数使用多少次，直到总和大于target为止，递归出口是：总和等于target，或者总和大于target，或者递归位置大于数组的最后一个元素的位置。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates,target,0,0);return vv;}void dfs(vector<int>& candidates, int target,int pos,int sum){if(sum==target){vv.push_back(v);return;}if(sum>target || pos==candidates.size()) return;//枚举每个数的个数for(int k=0;k*candidates[pos]+sum<=target;k++){if(k) v.push_back(candidates[pos]);dfs(candidates,target,pos+1,sum+k*candidates[pos]);}//恢复现场for(int k=1;k*candidates[pos]+sum<=target;k++)v.pop_back();}
};

字母大小全排列

题目

思路

解决这道题依旧是使用DFS，对于是数字的位置不做任何处理，针对每个位置无非是两种情况，如果是小写字母，可以依旧是小写字母，也可以转换成大写字母；如果是大写字母，可以依旧是大写字母，也可以转换成小写字母。

代码

class Solution {vector<string> ret;public:vector<string> letterCasePermutation(string s) {string str;dfs(s,0,str);return ret;}void dfs(string& s,int pos,string str){if(pos==s.size()){ret.push_back(str);return;}char ch=s[pos];//不改变dfs(s,pos+1,str+ch);//改变if(ch>'9'){ch=change(ch);dfs(s,pos+1,str+ch);}}char change(char ch){if(ch>='a' && ch<='z') ch-=32;else if(ch>='A' && ch<='Z') ch+=32;return ch;}
};

优美的排列

题目

思路

解决这道题依旧是使用DFS，因为每个数字只能被使用一次，因此每使用一个数字，都需要对该数字进行标记，递归的出口是递归位置是第n+1个位置，递归时，从头到尾扫描，看该位置的值是否被使用过且满足要么perm[i]能够被i整除，要么i能被perm[i]整除。

代码

class Solution {bool vis[16];int ret;
public:int countArrangement(int n) {dfs(n,1);return ret;}void dfs(int n,int pos){if(pos==n+1){ret++;return;}for(int i=1;i<=n;i++){if(!vis[i] && (i%pos==0 || pos%i==0)){vis[i]=true;dfs(n,pos+1);vis[i]=false;}}}
};