目录
题目链接：组合
回溯本身就是递归的一种，只不过是在递归基础上加上了递归前和递归后的代码，而组合就是1 - n的范围内排列组合。
for循环是为了将每种情况遍历到，然后回溯的处理是为了将每一种情况容纳进去。
vector<vector<int>> res;
vector<int> path;
void backtracking(int n, int k, int i)
{
if(path.size() == k){
res.push_back(path);
return;
}
for(; i<=n; i++){
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return res;
}其实就是再for循环的判断条件中加了一个，n - (k - path.size()) + 1。
假设n = 4, k = 4,这样，第一层从2开始得遍历都没有意义了，第二层从3开始得遍历都没意义了，第三层从4开始没有意义。
?+ 1 是因为包括起点位置，左闭所以加一。
for(; i<=n - (k - path.size()) + 1; i++){
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}题目链接：组合总和Ⅲ
这个就是在上面一道题的基础上加了sum用来记录路径上的和，同时因为题目中说了只要1 - 9的数字，因此for循环的限定条件为i <= 9。
vector<vector<int>> res;
vector<int> path;
void backtracking(int k, int n, int i, int sum)
{
if(path.size() == k){
if(sum == n)res.push_back(path);
return;
}
for(; i <= 9; i++){
path.push_back(i);
sum += i;
backtracking(k, n, i + 1, sum);
sum -= i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1, 0);
return res;
}其实很简单，在backtracking()函数最上面加个这就可以，可以避免没必要的选取。
if(sum > n) return;题目链接：组合总和Ⅰ
本题与组合总和Ⅲ的区别就是区间的数可重复使用，同时给的数不是从1开始递增的，所以我们进行代码实现的时候，应该传入i，这样可保证前面的一定是相对小的，后面的是大的，最终加和是target而且不会重复。
void backtracking(vector<int>& candidates, int target, int sum, int index)
{
if(sum > target) return;
if(sum == target) {
res.push_back(path);
return;
}
for(int i = index; i<candidates.size(); i++){
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, target, 0, 0);
return res;
}我们在for循环上进行处理，这样就可以减少进入循环的次数，从而实现优化。
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)题目链接：组合总和Ⅱ
如果我们直接提交这个代码，部分数据会超时，所以，我们应该用上上道题目的剪枝优化。
void backtracking(vector<int>& candidates, int target, int sum, int i, vector<bool>& used)
{
if(sum == target){
res.push_back(path);
return;
}
for(; i < candidates.size(); i++){
if(i > 0 && candidates[i] == candidates[i -1] && used[i - 1] == false){
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used);
used[i] = false;
path.pop_back();
sum -= candidates[i];
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(), false);
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return res;
}将for循环里面改成这样就可以了。
for(; i < candidates.size() && sum + candidates[i] <= target; i++)题目链接：电话号码组合
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
vector<string> res;
string s;
void backtracking(string& digits, int index)
{
if(index == 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]);
backtracking(digits, index + 1);
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return res;
backtracking(digits,0);
return res;
}组合问题中，我们通过组合，知道了组合问题的模板和剪枝思路，
然后组合总和Ⅲ中，我们知道了（数组中无重复数字，数组中不可重复使用）sum在回溯过程中求和的写法
之后组合总和中， 我们解决了一个数组中数字可重复使用（数组中无重复数字）的加和问题，
然后组合总和Ⅱ中， 我们解决了一个数组中数字只能使用一次（数组中有重复数字）的问题，引入了used的bool数组来判断。
最后的电话号码则是一个和上面类似，同时可以练习练习string的用法。
题目链接分割回文串
我们将判断是不是回文串的函数先分离出来，然后再根据回文的坐标判断。
所谓分割，就是根据循环的 i 的变化和传入的初始值的变化来控制。
vector<vector<string>> res;
vector<string> path;
bool is_reverse(const string& s, int i, int j)
{
while(i < j){
if(s[i] != s[j]) return false;
i ++; j--;
}
return true;
}
void backtracking(string& s, int index)
{
if(index >= s.size()){
res.push_back(path);
return;
}
for(int i = index; i < s.size(); i++){
if(is_reverse(s,index, i)){
string str = s.substr(index, i - index + 1);
path.push_back(str);
backtracking(s, i + 1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return res;
}题目链接：复原ip地址
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
void backtracking( string& s, 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() + 1 + i, '.');
pointnum ++;
backtracking(s, i + 2, pointnum);
pointnum --;
s.erase(s.begin() + 1 + i);
}
else break;
}
}
vector<string> restoreIpAddresses(string s) {
backtracking(s, 0, 0);
return res;
}分割类型的问题，其思路基本都是将每一小部分判断的函数分离出来，然后将判断加入到主函数中，进行分割保存。
题目链接：子集Ⅰ
本题和组合总和有点相似，不同是我们集合要取得是每一层的集合，而组合总和只要符合条件的集合。所以我们path放入res的步骤改到了递归代码的下面。
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, int index)
{
if(index >= nums.size()) return;
for(int i = index; i < nums.size(); i++){
path.push_back(nums[i]);
backtracking(nums, i + 1);
res.push_back(path);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
res.push_back(path);
return res;
}上面的代码，我们的存储集合是由大到小的存储。
下面的代码，我们的存储集合是由小到大的存储。?
void backtracking(vector<int>& nums, int index)
{
res.push_back(path);
if(index >= nums.size()) return;
for(int i = index; i < nums.size(); i++){
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}题目链接：子集Ⅱ
本题去重逻辑和组合总和Ⅱ有很大相似。
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, int index, vector<bool>& used)
{
res.push_back(path);
if(index >= nums.size()) return;
for(int i = index; i < nums.size(); i++){
if(i > 0 && used[i - 1] == false && nums[i - 1] == nums[i]) continue;
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, 0, used);
return res;
}set去重比起used数组来说简单许多，这也取决于set本身的特性，善于利用stl容器可以使得代码简洁。
void backtracking(vector<int>& nums, int index)
{
res.push_back(path);
if(index >= nums.size()) return;
unordered_set<int> uset;
for(int i = index; i < nums.size(); i++){
if(uset.find(nums[i]) != uset.end()){
continue;
}
path.push_back(nums[i]);
uset.insert(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
子集问题其实和组合的代码很相似，区别就是，组合一般最后才放结果，而子集问题在每一次遍历都会放入结果，
子集Ⅰ主要就是一个数组五重复数字（不需要去重） 的数组求解。
子集Ⅱ是一个数组有重复数字（需要去重）的数组的子集求解。
题目链接：全排列Ⅰ
排列的特点就是可以有重复的集合，但是每个集合中的数的顺序必须不一样。
本题特点就是当前层用过的数字在接下来的层就不可以用了，
也就是数组中的数不可重复使用（需要去重）。两个集合元素可以相同，但是顺序可以不同。
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, int index, vector<bool>& used)
{
if(path.size() == nums.size()){
res.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++){
if(used[i] == true) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, 0, used);
return res;
}题目链接：全排列Ⅱ
本题目就是数组中有重复数字，同时重复数字可重复使用的题目。
使用used树层去重的逻辑是使用used[i - 1] == false。
使用used树枝去重的逻辑是使用used[ i ] == true。
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, 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){
used[i] = true;
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, used);
used[i] = false;
path.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, used);
return res;
}排列问题中for循环都是从?0开始的，同时used[]中的去重和组合中有相同的逻辑。
排列、组合、集合这三个部分代码有很多相似处，但是细节有很大的差别。
题目链接：N皇后
我们重点判断的函数单拿出来，别的部分和普通回溯的代码一摸一样。
判断重复的部分我们只探讨左上、右上、正上方是否重复，下方不需要判断，因为如果不合适，回溯部分会自动剔除不合适的情况。
（本题属于一维的递归）。
vector<vector<string>> res;
bool isvalid(int row, int col, vector<string>& path, int n){
for(int i = row - 1; i>=0; i--){//直线范围判重
if(path[i][col] == 'Q') return false;
}
//45度角判重
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
if(path[i][j] == 'Q') return false;
}
//135度角
for(int i = row - 1, j = col + 1; i >= 0 && j < n; j++, i--){
if(path[i][j] == 'Q') return false;
}
return true;
}
void backtracking(int n,vector<string>& path, int row){
if(row == n){
res.push_back(path);
return;
}
for(int col = 0; col < n; col++){
if(isvalid(row, col, path, n)){
path[row][col] = 'Q';
backtracking(n, path, row + 1);
path[row][col] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> path(n, string(n, '.'));
backtracking(n, path, 0);
return res;
}题目链接：解数独
这里最重要的就是需要同时判断行和列，N皇后是只需要判断每行，因此，解数独需要多加一层for循环，后面的步骤就和上面一样了，处理判断条件的函数isValid()。
之后，我们通过backtracking()的返回为真还是假来判断是否成立。最后的结果存在了board中。
（本题为二维的递归）
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) { // 遍历行
for (int j = 0; j < board[0].size(); j++) { // 遍历列
if (board[i][j] == '.') {
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
if (isValid(i, j, k, board)) {
board[i][j] = k; // 放置k
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯，撤销k
}
}
return false; // 9个数都试完了，都不行，那么就返回false
}
}
}
return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) { // 判断行里是否重复
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) { // 判断列里是否重复
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}这类问题，我们涉及到一维还是二维的问题，同时，我们处理的主要逻辑还是回溯的思维，将判断成立条件的函数独立出来，最后实现解题，
该搜索问题特点是单层不可重复使用相同元素，同时path.size() > 1 的部分都可以被收入答案。
单层使用set去重。
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, int index)
{
if(path.size() > 1){
res.push_back(path);
}
unordered_set<int> uset;
for(int i = index; i < nums.size(); i++){
if(!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end()){
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return res;
}回溯整体来说，涉及一个递归前和递归后的处理，还有常用的模板，这些题目的模板多刷几次，思路理通顺了，见到这类问题可以很好的解决。回溯中的代码相似性还是很多的。