# 代码随想录-回溯算法

```#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>

using namespace std;

template<typename T>
void print(const vector<T>& nums)
{
for(auto&& num : nums)
{
cout << num << " ";
}
cout << endl;
cout << "=====" << endl;
}

template<typename T>
void print(const vector<vector<T>>& vecs)
{
for(const vector<T>& nums : vecs)
{
for(auto num : nums)
{
cout << num << " ";
}
cout << endl;
}
cout << "=====" << endl;
}

void backtrack(int n, int k, vector<int>&path,vector<vector<int>>&res, int index)
{
if(path.size() == k)
{
res.push_back(path);
return;
}
for(int i = index; i <= n; ++i)
{
path.push_back(i);
backtrack(n,k,path,res,i + 1);
path.pop_back();
}
}

void backtrack_jianzhi(int n, int k, vector<int>&path,vector<vector<int>>&res, int index)
{
if(path.size() == k)
{
res.push_back(path);
return;
}
for(int i = index; i <= n - (k - path.size()) + 1; ++i)
{
path.push_back(i);
backtrack_jianzhi(n,k,path,res,i + 1);
path.pop_back();
}
}

vector<vector<int>>combine(int n, int k)
{
vector<vector<int>>res;
vector<int>path;
// backtrack(n,k,path,res,1);
backtrack_jianzhi(n,k,path,res,1);
return res;
}

void backtrack(int n, int k, vector<int>&path,vector<vector<int>>&res,int sum, int index)
{
if(path.size() == k)
{
if(sum == n)
{
res.push_back(path);
}
return ;
}
for(int i = index; i <= 9; ++i)
{
path.push_back(i);
sum += i;
backtrack(n,k,path,res,sum,i + 1);
sum -= i;
path.pop_back();
}
return;
}

void backtrack_jianzhi(int n, int k, vector<int>&path,vector<vector<int>>&res,int sum, int index)
{
if(sum > n)return;
if(path.size() == k)
{
if(sum == n)
{
res.push_back(path);
}
return ;
}
for(int i = index; i <= 9 - (path.size() - k) + 1; ++i)
{
path.push_back(i);
sum += i;
backtrack_jianzhi(n,k,path,res,sum,i + 1);
sum -= i;
path.pop_back();
}
return;
}

vector<vector<int>>combinationSum3(int n, int k)
{
vector<vector<int>>res;
vector<int>path;
backtrack_jianzhi(n,k,path,res,0,1);
// backtrack(n,k,path,res,0,1);
return res;
}

string letterMap[10]={
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"};

void backtrack(const string & digits, string& s, vector<string>& res,int index)
{
if(s.size() == digits.size())
{
res.push_back(s);
return;
}
int digit = digits[index] - '0';
string letter = letterMap[digit];
for(int i = 0; i < letter.size(); ++i)
{
s.push_back(letter[i]);
backtrack(digits,s,res,index + 1);
s.pop_back();
}
}

vector<string> letterCombinations(const string& digits)
{
vector<string>res;
if(digits.size() == 0)return res;
string s;
backtrack(digits,s,res,0);
return res;
}

void backtrackI(const vector<int>& candidates,int target,vector<int>&path,vector<vector<int>>&res,int sum, int index)
{
if(sum > target)return;
if(sum == target)
{
res.push_back(path);
return;
}
for(int i = index ; i < candidates.size(); ++i)
{
sum += candidates[i];
path.push_back(candidates[i]);
backtrackI(candidates,target,path,res,sum,i);
path.pop_back();
sum -= candidates[i];
}

}

vector<vector<int>>combinationSum(const vector<int>& candidates, int target)
{
vector<vector<int>>res;
vector<int>path;
backtrackI(candidates,target,path,res,0,0);
return res;
}

void backtrack(const vector<int>&candidiates,vector<int>&path,vector<vector<int>>&res,int \
target,int sum,int index,vector<bool>&used)
{
if(sum == target)
{
res.push_back(path);
return;
}
for(int i = index; i < candidiates.size() && sum + candidiates[i] <= target ; ++i)
{
if(i > 0 && candidiates[i] == candidiates[i-1] && used[i-1] == false)
{
continue;
}
path.push_back(candidiates[i]);
sum += candidiates[i];
used[i] = true;
backtrack(candidiates,path,res,target,sum,i+1,used);
used[i] = false;
sum -= candidiates[i];
path.pop_back();
}
}

vector<vector<int>>combinationSum2(vector<int>&candidates,int target)
{
vector<bool>used(candidates.size(),false);
vector<int>path;
vector<vector<int>>res;
sort(candidates.begin(),candidates.end());
backtrack(candidates,path,res,target,0,0,used);
return res;

}

bool isHuiWen(string s, int left,int right)
{
for(int i = left,j = right ; i < j; ++i,--j)
{
if(s[i] != s[j])return false;
}
return true;
}

void backtrack(string s, int index, vector<vector<string>>&res,vector<string>&path)
{
if(index >= s.size())
{
res.push_back(path);
return ;
}
for(int i = index; i < s.size(); ++i)
{
if(isHuiWen(s,index,i))
{
string str = s.substr(index,i - index + 1);
path.push_back(str);
}
else{
continue;
}
backtrack(s,i + 1,res,path);
path.pop_back();
}
}

vector<vector<string>>partition(string s)
{
vector<vector<string>>res;
vector<string>path;
backtrack(s,0,res,path);
return res;

}

bool isValid(const string s,int start,int end)
{
if(start > end)return false;
if(s[start] == '0' && start != end)
{
return false;
}
int num = 0;
for(int i = start; i <= end; ++i)
{
if(s[i] < '0' || s[i] > '9')return false;
num = 10 * num + s[i] - '0';
if(num > 255)
{
return false;
}
}
return true;
}

void backtrack(string& s, string& path,vector<string>&res,int index,int pointnum)
{
if(pointnum == 3)
{
if(isValid(s,index,s.size() - 1))
{
res.push_back(s);
}
return;
}
for(int i = index;i < s.size(); ++i)
{
if(isValid(s,index,i))
{
s.insert(s.begin() + i + 1,'.');
++pointnum;
backtrack(s,path,res,i + 2, pointnum);
--pointnum;
s.erase(s.begin() + i + 1);
}
}

}

{
vector<string>res;
string path;
backtrack(s,path,res,0,0);
return res;

}

void backtrack_sub(const vector<int>& nums,vector<vector<int>>&res,vector<int>&path,int index)
{
res.push_back(path);
if(index >= nums.size())
{
return;
}
for(int i = index; i < nums.size(); ++i)
{
path.push_back(nums[i]);
backtrack_sub(nums,res,path,i+1);
path.pop_back();
}
}

vector<vector<int>>subset(const vector<int>& nums)
{
vector<vector<int>>res;
vector<int>path;
backtrack_sub(nums,res,path,0);
return res;
}

void backtrack_sequence(const vector<int>& nums,vector<int>path,vector<vector<int>>&res,int index)
{
if(path.size() > 1)
{
res.push_back(path);
}
unordered_set<int>set;
for(int i = index; i < nums.size();++i)
{
if((!path.empty() && nums[i] < path.back()) || set.find(nums[i])!=set.end())continue;
set.insert(nums[i]);
path.push_back(nums[i]);
backtrack_sequence(nums,path,res,i + 1);
path.pop_back();
}
}

vector<vector<int>>findSubSquences(const vector<int>& nums)
{
vector<int>path;
vector<vector<int>>res;
backtrack_sequence(nums,path,res,0);
return res;
}

void backtrack(const vector<int>& nums,vector<int>&path,vector<vector<int>>&res,vector<bool>&used)
{
if(path.size() == nums.size())
{
res.push_back(path);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
if(used[i])continue;
path.push_back(nums[i]);
used[i] = true;
backtrack(nums,path,res,used);
used[i] = false;
path.pop_back();
}
}

vector<vector<int>>permute(const vector<int>& nums)
{
vector<vector<int>>res;
vector<int>path;
vector<bool>used(nums.size(),false);
backtrack(nums,path,res,used);
return res;
}

void backtrack_permute(const vector<int>&nums,vector<int>&path,vector<vector<int>>&res,vector<bool>&used)
{
if(path.size() == nums.size())
{
res.push_back(path);
return;
}

for(int i = 0; i < nums.size(); ++i)
{
if(i > 0 && nums[i] == nums[i-1] && used[i-1]== false)continue;
if(used[i] == false)
{
path.push_back(nums[i]);
used[i] = true;
backtrack_permute(nums,path,res,used);
used[i] = false;
path.pop_back();
}
}
}

vector<vector<int>>permuteII(const vector<int>& nums)
{
vector<vector<int>>res;
vector<int>path;
vector<bool>used(nums.size(),false);
backtrack_permute(nums,path,res,used);
return res;
}

void backtrack_subset(const vector<int>& nums,vector<int>&path,vector<vector<int>>&res,vector<bool>&used,int index)
{
res.push_back(path);
unordered_set<int>set;
for(int i = index; i < nums.size(); ++i)
{
if(set.find(nums[i]) != set.end())continue;
set.insert(nums[i]);
path.push_back(nums[i]);
backtrack_subset(nums,path,res,used,i + 1);
path.pop_back();
}
}

vector<vector<int>>subsetII(const vector<int>& nums)
{
vector<vector<int>>res;
vector<int>path;
vector<bool>used(nums.size(),false);
backtrack_subset(nums,path,res,used,0);
return res;
}

bool isValid(int row,int col,vector<string>&chessboard,int n)
{
for(int i = 0; i < row; ++i)
{
if(chessboard[i][col] == 'Q')
return false;
}
for(int i = row - 1,j = col - 1; i >= 0 && j >= 0; --i,--j)
{
if(chessboard[i][j] == 'Q')
return false;
}
for(int i = row - 1,j = col + 1; i >= 0 && j < n; --i,++j)
{
if(chessboard[i][j] == 'Q')
return false;
}
return true;
}

void backtrack_help(vector<string>&chessboard,vector<vector<string>>&res,int row,int n)
{
if(row == n)
{
res.push_back(chessboard);
return;
}
for(int col = 0; col < n; ++col)
{
if(isValid(row,col,chessboard,n))
{
chessboard[row][col] = 'Q';
backtrack_help(chessboard,res,row+1,n);
chessboard[row][col] = '.';
}
}
}

vector<vector<string>>solveNqueens(int n)
{
vector<vector<string>>res;
vector<string>chessboard(n,string(n,'.'));
backtrack_help(chessboard,res,0,n);
return res;

}

bool isValid_sudoku(int row,int col,const vector<string>&board,char k)
{
for(int i = 0; i < 9; ++i)
{
if(board[i][col] == k)return false;
}
for(int j = 0; j < 9; ++j)
{
if(board[row][j] == k)return false;
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for(int i = startRow; i < startRow + 3; ++i)
{
for(int j = startCol; j < startCol + 3; ++j)
{
if(board[i][j] == k)return false;
}
}
return true;
}

bool backtrack_sudoku(vector<string>&board)
{
int m = board.size(), n = board[0].size();
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(board[i][j]!='.')continue;
for(char k = '1'; k <= '9'; ++k)
{
if(isValid_sudoku(i,j,board,k))
{
board[i][j] = k;
if(backtrack_sudoku(board))return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}

vector<string> solveSudoku(vector<string>&board)
{

backtrack_sudoku(board);
return board;
}

bool backtrack(unordered_map<string,map<string,int>>&targets,vector<string>& res,int ticketNum)
{
if(res.size() == ticketNum + 1)
{
return true;
}
for(pair<const string,int>&target:targets[res[res.size() - 1]])
{
if(target.second > 0)
{
res.push_back(target.first);
--target.second;
if(backtrack(targets,res,ticketNum))return true;
++target.second;
res.pop_back();
}
}
return false;
}

vector<string>findItinerary(vector<vector<string>>&tickets)
{
vector<string>res;
unordered_map<string,map<string,int>>target;
for(const auto& ticket:tickets)
{
++target[ticket[0]][ticket[1]];
}
res.push_back("JFK");
backtrack(target,res,target.size());
return res;

}

int main()
{

//LeetCode77:组合
int n = 4, k = 2;
print(combine(n,k));

//LeetCode216 组合总和III(不重复)
k = 3, n = 7;
print(combinationSum3(n,k));

//LeetCode17 电话号码的字母组合
print(letterCombinations("23"));

//LeetCode39 组合总和(可重复)
vector<int>candidates{2,3,6,7};
int target = 7;
print(combinationSum(candidates,target));

//LeetCode40 组合总和II（每个数字在每个组合中只能使用一次)
candidates = {2,5,2,1,2};
target = 5;
print(combinationSum2(candidates,target));

//LeetCode131分割回文串
string s = "aab";
print<string>(partition(s));

//LeetCode93复原所有IP地址

//LeetCode78 子集
vector<int>nums{1,2,3};
print(subset(nums));

//LeetCode90 子集II
nums = {1,2,2};
print(subsetII(nums));

//LeetCode491 递增子序列
nums = {4,6,7,7};
print(findSubSquences(nums));

//LeetCode46 全排列
nums = {1,2,3};
print(permute(nums));

//LeetCode47 全排列II
nums = {1,1,2};
print(permuteII(nums));

//LeetCode332 重新安排行程
vector<vector<string>>tickets{{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
print(findItinerary(tickets));

//LeetCode51 N皇后
print<string>(solveNqueens(4));

//LeetCode37 解数独
vector<string>board{
"53..7....",
"6..195...",
".98....6.",
"8...6...3",
"4..8.3..1",
"7...2...6",
".6....28.",
"...419..5",
"....8..79"
};
print<string>(solveSudoku(board));

return 0;
}```