搜索与回溯练习（一）
文章内容学习自代码随想录，感谢carl！！！！
77. 组合 - 力扣（LeetCode）
不降原则处理组合数问题
vector<vector<int>> ans;
vector<int> path;
void dfs(int n,int k,int start){
if(path.size()==k){
ans.push_back(path);
return;
}
for(int i=start;i<=n-(k-path.size())+1;i++){
//剪枝n-(k-path.size())+1,表示至多开始的位置，超过这个位置凑不到k个
path.push_back(i);
dfs(n,k,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
dfs(n,k,1);
return ans;
}
216. 组合总和 III - 力扣（LeetCode）
依然是不降原则处理组合数
vector<vector<int>> ans;
vector<int> path;
void dfs(int n,int k,int start,int sum){
if(sum>n) return;//剪枝,如果sum,已经大于n了，那么就不用再找了，直接回溯
if(path.size()==k){
if(n==sum) ans.push_back(path);
return;
}
for(int i=start;i<=9;i++){
path.push_back(i);
dfs(n,k,i+1,sum+i);
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
dfs(n,k,1,0);
return ans;
}
以上两题都是在一个集合里面选取n个数，我们需要用一个start来标记，即利用不降原则挑选出不同的组合
17. 电话号码的字母组合 - 力扣（LeetCode）
本题是在多个集合里面选取，不需要标记开始位置来去重
string str[10]={
" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> ans;
string path;
void dfs(string digits,int step)
{
if(path.size()==digits.size()){
ans.push_back(path);
return;
}
string s=str[digits[step]-'0'];
for(int i=0;i<s.size();i++){
path+=s[i];
dfs(digits,step+1);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return ans;//空串的情况
dfs(digits,0);
return ans;
}
39. 组合总和 - 力扣（LeetCode）
vector<vector<int>> ans;
vector<int> path;
void dfs(vector<int>& candidates,int target,int sum,int start)
{
if(sum>target) return;
if(sum==target){
ans.push_back(path);
return;
}
for(int i=start;i<candidates.size();i++){
path.push_back(candidates[i]);
dfs(candidates,target,sum+candidates[i],i);//注意此处的不降原则用i，不用i+1,表示这个数可以继续选
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(candidates,target,0,0);
return ans;
}
以上这些题都是不包含重复元素的，那如果由重复元素我们又该怎么做呢？
40. 组合总和 II - 力扣（LeetCode）
像这道题他有重复的元素，却要求挑出来不能有重复的组合
vector<vector<int>> ans;
vector<int> path;
void dfs(vector<int>& candidates,int target,int sum,int start)
{
if(sum>target) return;
if(sum==target){
ans.push_back(path);
return;
}
for(int i=start;i<candidates.size();i++){
if(i>start&&candidates[i-1]==candidates[i]) continue;//如果本层搜索的首位和前一层相同则剪枝
path.push_back(candidates[i]);
dfs(candidates,target,sum+candidates[i],i+1);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
if(candidates[0]>target) return {
};
dfs(candidates,target,0,0);
return ans;
}
131. 分割回文串 - 力扣（LeetCode）
vector<vector<string>> ans;
vector<string> path;
bool ishuiwen(string s,int sta,int end){
while(sta<=end)
{
if(s[sta]==s[end]){
sta++;
end--;
}
else return false;
}
return true;
}
void dfs(string s,int start)
{
if(start==s.size()){
ans.push_back(path);
return;
}
for(int i=start;i<s.size();i++){
if(ishuiwen(s,start,i)){
string x=s.substr(start,i-start+1);
path.push_back(x);
dfs(s,i+1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
dfs(s,0);
return ans;
}
93. 复原 IP 地址 - 力扣（LeetCode）
注意什么是非法的ip地址，数字大于255非法，数字开头为0也是非法的
vector<string> ans;
bool isip(string s,int start,int end)
{
if(start>end) return false;
if(s[start]=='0'&&start!=end) return false;
int sum=0;
for(int i=start;i<=end;i++){
if(s[i]<'0'||s[i]>'9') return false;
sum=sum*10+(s[i]-'0');
if(sum>255) return false;
}
return true;
}
void dfs(string s,int start,int cnt,string path)
{
if(cnt==3){
//cnt是拿来数点的个数的，数到3个
if(isip(s,start,s.size()-1)){
path+=s.substr(start,s.size()-start);
ans.push_back(path);
}
return;
}
for(int i=start;i<s.size();i++){
if(isip(s,start,i)){
dfs(s,i+1,cnt+1,path+s.substr(start,i-start+1)+".");
}
}
}
vector<string> restoreIpAddresses(string s) {
dfs(s,0,0,"");
return ans;
}
