目录
组合
目标和
组合总和
字母大小全排列
组合
题目
思路
解决这道题利用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;}}}
};