代码随想录day24

        回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作。

        回溯法，一般可以解决如下几种问题：

        1、组合问题：N个数里面按一定规则找出k个数的集合

        2、切割问题：一个字符串按一定规则有几种切割方式

        3、子集问题：一个N个数的集合里有多少符合条件的子集

        4、排列问题：N个数按一定规则全排列，有几种排列方式

        5、棋盘问题：N皇后，解数独等等

回溯法模版：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合问题

77. 组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

        根据模版，得出代码：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtravel(int n,int k,int start){
        if(path.size()==k){
            res.push_back(path);
            return;
        }
        for(int i=start;i<=n;++i){
            path.push_back(i);//处理节点
            backtravel(n,k,i+1);//递归
            path.pop_back();//回溯
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtravel(n,k,1);
        return res;
    }
};

        配合剪枝操作进行优化：如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。所以起始位值至多从n-（k-path.size())+1开始。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtravel(int n,int k,int start){
        if(path.size()==k){
            res.push_back(path);
            return;
        }
        for(int i=start;i<=n-(k-path.size())+1;++i){
            path.push_back(i);//处理节点
            backtravel(n,k,i+1);//递归
            path.pop_back();//回溯
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtravel(n,k,1);
        return res;
    }
};

216.组合总和III  

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtravel(int k,int n,int sum,int start){
        if(path.size()==k&&sum==n){
           res.push_back(path); 
           return; 
        }
        for(int i=start;i<=9;++i){
            sum+=i;
            path.push_back(i);
            backtravel(k,n,sum,i+1);
            path.pop_back();
            sum-=i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtravel(k,n,0,1);
        return res;
    }
};

17.电话号码的字母组合 

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

        回溯法来解决n个for循环的问题,因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合。

class Solution {
public:
    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;
    void backtravel(string digits,int idx,string s){
        if(idx==digits.size()){
            res.push_back(s);
            return;
        }
        int digit=digits[idx]-'0';
        string letter=letterMap[digit];
        for(int i=0;i<letter.size();++i){
            backtravel(digits,idx+1,s+letter[i]);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return res;
        backtravel(digits,0,"");
        return res;
    }
};

39. 组合总和

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

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。

示例 1：

• 输入：candidates = [2,3,6,7], target = 7,
• 所求解集为： [ [7], [2,2,3] ]

        此题特殊之处为每个数字可以重复选取，故每次返回的初值为i，而不是i+1。

class Solution {
public:
   vector<vector<int>> result;
    vector<int> path;
    int sum=0;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum>target) {
            return;
        }
        if (sum==target) {
            result.push_back(path);
            return;
        }

        for (int i=startIndex; i<candidates.size(); i++) {
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
            sum-=candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, sum, 0);
        return result;
    }
};

        优化后：排序之后，如果sum+candidates[i]>target直接剪枝。

class Solution {
public:
   vector<vector<int>> result;
    vector<int> path;
    int sum=0;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum>target) {
            return;
        }
        if (sum==target) {
            result.push_back(path);
            return;
        }

        for (int i=startIndex; i<candidates.size()&&sum+candidates[i]<=target; i++) {
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
            sum-=candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, sum, 0);
        return result;
    }
};

40.组合总和II 

给定一个数组 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]]

         集合（数组candidates）有重复元素，但还不能有重复的组合。元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

        如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    int sum=0;
    void backtravel(vector<int> candidates,int sum,int target,int start,vector<bool> used){
        if(sum>target) return;
        if(sum==target){
            res.push_back(path);
            return;
        }
        for(int i=start;i<candidates.size()&&sum+candidates[i]<=target;++i){
            if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
                // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
                // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
                //在同一树层使用过的相同元素跳过
                continue;
            }
            used[i]=true;
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtravel(candidates,sum,target,i+1,used);
            path.pop_back();
            sum-=candidates[i];
            used[i]=false;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(),false);
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(),candidates.end());
        backtravel(candidates,sum,target,0,used);
        return res;
    }
};

        另外，用start进行去重的写法。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    int sum=0;
    void backtravel(vector<int> candidates,int sum,int target,int start){
        if(sum>target) return;
        if(sum==target){
            res.push_back(path);
            return;
        }
        for(int i=start;i<candidates.size()&&sum+candidates[i]<=target;++i){
           // 要对同一树层使用过的元素进行跳过
            if (i>start&& candidates[i]==candidates[i-1]) {
                continue;
            }
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtravel(candidates,sum,target,i+1);
            path.pop_back();
            sum-=candidates[i];
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(),candidates.end());
        backtravel(candidates,sum,target,0);
        return res;
    }
};

分割问题

131.分割回文串 

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

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

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

class Solution {
public:
    vector<string> path;
    vector<vector<string>> res;
    bool isPalindrome(string s,int start,int end){
        while(start<end){
            if(s[start]!=s[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    void backtarvel(string &s,int start){
        if(start>=s.size()){
            //start遍历到叶子节点
            res.push_back(path);
            return;
        }
        for(int i=start;i<s.size();++i){
            if(isPalindrome(s,start,i)){
                //只有当子串是回文子串时，才会被压入路径中
                string str=s.substr(start,i-start+1);
                path.push_back(str);
            }else{
                continue;
            }
            backtarvel(s,i+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtarvel(s,0);
        return res;
    }
};

93.复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 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"]

        返回条件：前面已添加了3个逗号，且第四个数字满足条件，才会加入result。

        注意，只有当前数字满足条件时才会继续进行判断，否则就直接跳过。 

class Solution {
public:
    vector<string> result;// 记录结果
    // 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;
    }
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

子集问题

78.子集

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

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

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

         此题在收集的时机方面与之前不同，不是在叶子节点的地方收集，而是在每一层都要收集。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtravel(vector<int> nums,int start){
        res.push_back(path);
        if(start>=nums.size()){
            return;
        }
        for(int i=start;i<nums.size();++i){
            path.push_back(nums[i]);
            backtravel(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtravel(nums,0);
        return res;
    }
};

90.子集II 

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

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

示例:

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

        使用used数组进行去重， 进行排序将重复的数字放在一起，然后用uesd进行判断是否在前一层树中已经使用过。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtravel(vector<int> nums,int start,vector<bool>& used){
        res.push_back(path);
        if(start>=nums.size()){
            return;
        }
        for(int i=start;i<nums.size();++i){
             if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtravel(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()); // 去重需要排序
        backtravel(nums,0,used);
        return res;
    }
};

491.递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]]

        因此题不能对数组进行排序，故之前那种去重方法不能使用。此题使用set进行去重，每一层树中都重新定义一个集合，进行去重，每一层都要进行收集。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtravel(vector<int> nums,int start){
        if(path.size()>1) res.push_back(path);
        unordered_set<int> uset; //使用set来对本层元素进行去重
        for (int i=start; 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]);
        backtravel(nums, i + 1);
        path.pop_back();
    }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtravel(nums,0);
        return res;
    }
};

排列问题

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

         此题需要去重操作，used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtravel(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(used[i]==true) continue;
            used[i]=true;
            path.push_back(nums[i]);
            backtravel(nums,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backtravel(nums,used);
        return res;
    }
};

47.全排列 II 

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

示例 1：

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

         此题中含有重复数字，去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtravel(vector<int> nums,vector<bool> &used){
        if(path.size()==nums.size()){
            res.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]);
                backtravel(nums,used);
                path.pop_back();
                used[i]=false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end()); //排序
        vector<bool> used(nums.size(),false);
        backtravel(nums,used);
        return res;
    }
};

332.重新安排行程

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

• 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
• 所有的机场都用三个大写字母表示（机场代码）。
• 假定所有机票至少存在一种合理的行程。
• 所有的机票必须都用一次 且 只能用一次。

示例 1：

• 输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
• 输出：["JFK", "MUC", "LHR", "SFO", "SJC"]

class Solution {
public:
    unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

棋盘问题

51. N皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}
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;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

class Solution {
private:
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);
    }
};