C++回溯法leetcode练习集-创新互联

按三步骤来，1.递归函数的返回值以及参数 2.先想递归的终止情况 3.回溯搜索的遍历过程，就是for循环里面的树的宽度，递归的深度构成了树的深度。
1.定义四个数组分别表示行，列，两个对角线；参数就是quene(i+1)一直搜索。2.递归的终止情况就是每个a[i]都有位置，此时i>n的，就进一步打印3.j从1开始，代表列，如果纵和两个对角线都没有被占领才可以进去搜索，最后需要回溯，退一格。

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

17.电话号码的字母组合

示例: 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序

class Solution {

private:
    const string letterMap[10]={
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
public:
    vectorresult;
    string s;
    void backtracking(const string& digits, int index) {
        if(index==digits.size()){
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for(int i=0;iletterCombinations(string digits) {
        if(digits.size() == 0) {
            return result;
        }
        backtracking(digits,0);
        return result;
    }
};

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。



示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

class Solution {
private:
    vector>result;
    vectorpath;
    void backtracking(vector& candidates,int target, int sum, int startIndex) {
        if(sum >target) {
            return;
        }
        if(sum==target)
        {
            result.push_back(path);
            return;
        }
        for(int i= startIndex;i>combinationSum(vector& candidates, int target) {
        backtracking(candidates,target,0,0);
        return result;
    }
};

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。

示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [   [1,2,2],   [5] ]

class Solution {
private:
    vector>result;
    vectorpath;
    void backtracking(vector& candidates,int target, int sum,int startIndex ,vector& used){
        if(sum>target)
        return;
        if(sum==target){
        result.push_back(path);
        return;
        }
        for(int i=startIndex;i0&&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;
            sum-=candidates[i];
            path.pop_back();
        }
    }
public:
    vector>combinationSum2(vector& candidates, int target) {
        vectorused(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        backtracking(candidates,target,0,0,used);
        return result;
    }
};

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

class Solution {
private:
    vector>result;
    vectorpath; // 放已经回文的子串
    void backtracking (const string& s, int startIndex) {
        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i< s.size(); i++) {
            if (isPalindrome(s, startIndex, i)) {   // 是回文子串
                // 获取[startIndex,i]在s中的子串
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {                                // 不是回文，跳过
                continue;
            }
            backtracking(s, i + 1); // 寻找i+1为起始位置的子串
            path.pop_back(); // 回溯过程，弹出本次已经填在的子串
        }
    }
    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i< j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }
public:
    vector>partition(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "1111"
输出：["1.1.1.1"]
示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"

class Solution {
private:
    vectorresult;// 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i< s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    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;
    }
public:
    vectorrestoreIpAddresses(string s) {
        result.clear();
        if (s.size()< 4 || s.size() >12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

解题思路：

DFS 和回溯算法区别

DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

何时使用回溯算法

当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

3.怎么样写回溯算法(从上而下，※代表难点，根据题目而变化)

①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
②根据题意，确立结束条件
③找准选择列表(与函数参数相关),与第一步紧密关联※
④判断是否需要剪枝
⑤作出选择，递归调用，进入下一层
⑥撤销选择

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

class Solution {
private:
    vector>ans;
    vectornum;
    void backstracking(vector& nums,int start){
        ans.push_back(num);
        if(start>=nums.size())
        return;
        for(int i=start;istart&&num[i]==num[i-1])
            // continue;
            num.push_back(nums[i]);
            backstracking(nums,i+1);
            num.pop_back();
        }
    }
public:
    vector>subsets(vector& nums) {
        sort(nums.begin(),nums.end());
        backstracking(nums,0);
        return ans;
    }
};

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

class Solution {
private:
    vector>ans;
    vectornum;
    void backtracking(vector& nums,int target) {
        ans.push_back(num);
        for(int i=target;itarget&&nums[i]==nums[i-1])
            continue;
            num.push_back(nums[i]);
            backtracking(nums,i+1);
            num.pop_back();
        }
    }
public:
    vector>subsetsWithDup(vector& nums) {
        sort(nums.begin(),nums.end());
        backtracking(nums,0);
        return ans;
    }
};

总结：子集、组合类问题，关键是用一个 start 参数来控制选择列表！！

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:

给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况

// 版本一
class Solution {
private:
    vector>result;
    vectorpath;
    void backtracking(vector& nums, int startIndex) {
        if (path.size() >1) {
            result.push_back(path);
            // 注意这里不要加return，要取树上的节点
        }
        unordered_setuset; // 使用set对本层元素进行去重
        for (int i = startIndex; 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();
        }
    }
public:
    vector>findSubsequences(vector& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

class Solution {
public:
    vector>result;
    vectorpath;
    void backtracking (vector& nums, vector& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i< nums.size(); i++) {
            if (used[i] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true; //标记过的元素本层循环不能用
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector>permute(vector& nums) {
        result.clear();
        path.clear();
        vectorused(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素了

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {
private:
    vector>result;
    vectorpath;
    void backtracking (vector& nums, vector& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i< nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过 
            // 如果同一树层nums[i - 1]使用过则直接跳过
            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]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector>permuteUnique(vector& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vectorused(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

比全排列多了个去重步骤

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include#include#include
using namespace std;
const int N = 10;
int n,path[N];//存储一条下来的数字
bool st[N]; //存当前位置有没有被用过
void dfs(int u) {
    if(u==n) 
    {
        for(int i = 0;i>n;
        dfs(0);
        return 0;
    }

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

#include#include#include 
using namespace std;
const int N =20;
int n;
bool col[N],dg[N],udg[N]; //列，对角线，反对角线
char g[N][N];//输出
void dfs(int u) {
    if(u==n)//当u走到最后一行
    {
        for(int i=0;i>n;
        for(int i=0;i