C++回溯法leetcode練習(xí)集-創(chuàng)新互聯(lián)

按三步驟來，1.遞歸函數(shù)的返回值以及參數(shù) 2.先想遞歸的終止情況 3.回溯搜索的遍歷過程，就是for循環(huán)里面的樹的寬度，遞歸的深度構(gòu)成了樹的深度。
1.定義四個(gè)數(shù)組分別表示行，列，兩個(gè)對(duì)角線；參數(shù)就是quene(i+1)一直搜索。2.遞歸的終止情況就是每個(gè)a[i]都有位置，此時(shí)i>n的，就進(jìn)一步打印3.j從1開始，代表列，如果縱和兩個(gè)對(duì)角線都沒有被占領(lǐng)才可以進(jìn)去搜索，最后需要回溯，退一格。

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

17.電話號(hào)碼的字母組合

示例: 輸入："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;
    }
};

給你一個(gè) 無重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個(gè)目標(biāo)整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個(gè) 數(shù)字可以 無限制重復(fù)被選取 。如果至少一個(gè)數(shù)字的被選數(shù)量不同，則兩種組合是不同的。 

對(duì)于給定的輸入，保證和為 target 的不同組合數(shù)少于 150 個(gè)。



示例 1：

輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個(gè)候選， 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;
    }
};

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

說明： 所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。 解集不能包含重復(fù)的組合。

示例 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;
    }
};

給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。

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

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

class Solution {
private:
    vector>result;
    vectorpath; // 放已經(jīng)回文的子串
    void backtracking (const string& s, int startIndex) {
        // 如果起始位置已經(jīng)大于s的大小，說明已經(jīng)找到了一組分割方案了
        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(); // 回溯過程，彈出本次已經(jīng)填在的子串
        }
    }
    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;
    }
};

給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成，且不能含有前導(dǎo) 0），整數(shù)之間用 '.' 分隔。

例如："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;// 記錄結(jié)果
    // startIndex: 搜索的起始位置，pointNum:添加逗點(diǎn)的數(shù)量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗點(diǎn)數(shù)量為3時(shí)，分隔結(jié)束
            // 判斷第四段子字符串是否合法，如果合法就放進(jìn)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] 這個(gè)區(qū)間的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一個(gè)逗點(diǎn)
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗點(diǎn)之后下一個(gè)子串的起始位置為i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯刪掉逗點(diǎn)
            } else break; // 不合法，直接結(jié)束本層循環(huán)
        }
    }
    // 判斷字符串s在左閉又閉區(qū)間[start, end]所組成的數(shù)字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start >end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0開頭的數(shù)字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i<= end; i++) {
            if (s[i] >'9' || s[i]< '0') { // 遇到非數(shù)字字符不合法
                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 和回溯算法區(qū)別

DFS 是一個(gè)勁的往某一個(gè)方向搜索，而回溯算法建立在 DFS 基礎(chǔ)之上的，但不同的是在搜索過程中，達(dá)到結(jié)束條件后，恢復(fù)狀態(tài)，回溯上一層，再次搜索。因此回溯算法與 DFS 的區(qū)別就是有無狀態(tài)重置

何時(shí)使用回溯算法

當(dāng)問題需要 “回頭”，以此來查找出所有的解的時(shí)候，使用回溯算法。即滿足結(jié)束條件或者發(fā)現(xiàn)不是正確路徑的時(shí)候(走不通)，要撤銷選擇，回退到上一個(gè)狀態(tài)，繼續(xù)嘗試，直到找出所有解為止

3.怎么樣寫回溯算法(從上而下，※代表難點(diǎn)，根據(jù)題目而變化)

①畫出遞歸樹，找到狀態(tài)變量(回溯函數(shù)的參數(shù))，這一步非常重要※
②根據(jù)題意，確立結(jié)束條件
③找準(zhǔn)選擇列表(與函數(shù)參數(shù)相關(guān)),與第一步緊密關(guān)聯(lián)※
④判斷是否需要剪枝
⑤作出選擇，遞歸調(diào)用，進(jìn)入下一層
⑥撤銷選擇

給你一個(gè)整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）。

解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。

示例 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;
    }
};

給定一個(gè)可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復(fù)的子集。

示例:

輸入: [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;
    }
};

總結(jié)：子集、組合類問題，關(guān)鍵是用一個(gè) start 參數(shù)來控制選擇列表?。?/p>遞增子序列

給定一個(gè)整型數(shù)組, 你的任務(wù)是找到所有該數(shù)組的遞增子序列，遞增子序列的長度至少是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]]
說明:

給定數(shù)組的長度不會(huì)超過15。
數(shù)組中的整數(shù)范圍是 [-100,100]。
給定數(shù)組中可能包含重復(fù)數(shù)字，相等的數(shù)字應(yīng)該被視為遞增的一種情況

// 版本一
class Solution {
private:
    vector>result;
    vectorpath;
    void backtracking(vector& nums, int startIndex) {
        if (path.size() >1) {
            result.push_back(path);
            // 注意這里不要加return，要取樹上的節(jié)點(diǎn)
        }
        unordered_setuset; // 使用set對(duì)本層元素進(jìn)行去重
        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]); // 記錄這個(gè)元素在本層用過了，本層后面不能再用了
            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;
    }
};

給定一個(gè) 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。

示例:

輸入: [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) {
        // 此時(shí)說明找到了一組
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i< nums.size(); i++) {
            if (used[i] == true) continue; // path里已經(jīng)收錄的元素，直接跳過
            used[i] = true; //標(biāo)記過的元素本層循環(huán)不能用
            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數(shù)組記錄path里都放了哪些元素了

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

示例 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) {
        // 此時(shí)說明找到了一組
        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;
    }
};

比全排列多了個(gè)去重步驟

給定一個(gè)整數(shù) n，將數(shù)字 1～n 排成一排，將會(huì)有很多種排列方法。

現(xiàn)在，請(qǐng)你按照字典序?qū)⑺械呐帕蟹椒ㄝ敵觥?
輸入格式
共一行，包含一個(gè)整數(shù) n。

輸出格式
按字典序輸出所有排列方案，每個(gè)方案占一行。

數(shù)據(jù)范圍
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];//存儲(chǔ)一條下來的數(shù)字
bool st[N]; //存當(dāng)前位置有沒有被用過
void dfs(int u) {
    if(u==n) 
    {
        for(int i = 0;i>n;
        dfs(0);
        return 0;
    }

n?皇后問題是指將 n 個(gè)皇后放在 n×n 的國際象棋棋盤上，使得皇后不能相互攻擊到，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。

現(xiàn)在給定整數(shù) n，請(qǐng)你輸出所有的滿足條件的棋子擺法。

輸入格式
共一行，包含整數(shù) n。

輸出格式
每個(gè)解決方案占 n 行，每行輸出一個(gè)長度為 n 的字符串，用來表示完整的棋盤狀態(tài)。

其中 . 表示某一個(gè)位置的方格狀態(tài)為空，Q 表示某一個(gè)位置的方格上擺著皇后。

每個(gè)方案輸出完成后，輸出一個(gè)空行。

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

輸出方案的順序任意，只要不重復(fù)且沒有遺漏即可。

數(shù)據(jù)范圍
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]; //列，對(duì)角線，反對(duì)角線
char g[N][N];//輸出
void dfs(int u) {
    if(u==n)//當(dāng)u走到最后一行
    {
        for(int i=0;i>n;
        for(int i=0;i