1.回溯算法.题目

题目
- 9.子集问题
- 10.子集||
- 11.递增子序列
- 12.全排列
- 13.全排列||
- 14.回溯算法去重问题的另外一个写法
- 15.重新安排行程
- 16.N皇后
总结
- 去重方式的不同

题目

9.子集问题

（题目链接）
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集，包含空集和子集）。说明：解集不能包含重复的子集，即不能存在元素组成一样的集合。
在这里插入图片描述
如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而==子集问题是找树的所有节点！==这与之前的组合问题不同，子集问题也是一种组合问题，它的集合时无序的（因此取过的元素不会重复取，在回溯算法时会用到startindex作为每层树的遍历起点）。

    std::vector<std::vector<int>> res;
    std::vector<int> path;
    void backtracking(std::vector<int>& nums, int startindex){
        //res.push_back(path); //加入这一行，则不用先加入空集，也能保证自身能在res中
        //其实不需要加终止条件，因为startindex>=nums.size()，本层循环就结束了
        if(startindex>=nums.size()) return; 
        for(int i=startindex; i<nums.size();i++){
            path.push_back(nums[i]);
            res.push_back(path);
            backtracking(nums, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        res.clear();
        path.clear();
        res.push_back(path);
        backtracking(nums, 0);
        return res;
    }

时间复杂度: O(n * 2^n)；空间复杂度: O(n)

10.子集||

（题目链接）
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。例如：输入: [1,2,2]，输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]。
这题与9.题的区别是给定集合里存在重复元素，而且求取的子集要去重；去重与6.组合||里的去重是一直的，所以理解“树层去重”和“树枝去重”非常重要。
在这里插入图片描述
从以上图解可以看出从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集。

    std::vector<std::vector<int>> res;
    std::vector<int> path;
    void backtracking(std::vector<int>& nums, int startindex, std::vector<bool> used){
        res.push_back(path);
        for(int i=startindex; 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;
            backtracking(nums, i+1, used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.clear();
        path.clear();
        std::vector<bool> used(nums.size(), false);
        std::sort(nums.begin(), nums.end());
        backtracking(nums, 0, used);
        return res;
    }

时间复杂度: O(n * 2^n)；空间复杂度: O(n)

11.递增子序列

（题目链接）
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]，给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
本题与之前的的求子集问题不同，这题是求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能用之前的去重逻辑！
在这里插入图片描述

    std::vector<std::vector<int>> res;
    std::vector<int> path;
    void backtracking(std::vector<int>& nums, int startindex){
        if(path.size()>1) res.push_back(path);
        std::unordered_set<int> uset; //使用set对本层元素去重
        for(int i=startindex; i<nums.size(); i++){
            // 当1.不是递增 2.已经在set中存在 则使用continue跳过本层这一递归
            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) {
        res.clear();
        path.clear();
        backtracking(nums, 0);
        return res;
    }

因为不能使用std::sort对给定数组进行nums预排列，所以不能使用std::vector<int> used布尔值数组的方式去重。

12.全排列

（题目链接）
给定一个 没有重复 数字的序列，返回其所有可能的全排列。不同于集合，排列时有序的，即 [1,2] 和 [2,1] 是两个集合。但排列问题需要一个used布尔值数组，标记已经选择的元素。
在这里插入图片描述
从上图可以看出，叶子节点就是得出结果的地方，即当path.size()==nums.size()时，长度一致时即得到了一种全排列的结果。

    std::vector<std::vector<int>> res;
    std::vector<int> path;
    void backtracking(std::vector<int>& nums, std::vector<bool> used){
        if(path.size()==nums.size()) {
            res.push_back(path);
        }
        for(int i=0; i<nums.size(); i++){
            if(used[i]==true) continue; //当历史层已经使用过该位置的元素时，则跳过本层中该次递归。
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        res.clear();
        path.clear();
        std::vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }

排列问题的不同：每层都是从0开始搜索而不是startIndex，需要used数组记录path里都放了哪些元素了.

13.全排列||

（题目链接）
给定一个 可包含重复数字 的序列 nums ，按任意顺序返回所有不重复的全排列。例如：输入：nums = [1,1,2]；输出： [[1,1,2], [1,2,1], [2,1,1]]。因此本题又涉及去重，要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
在这里插入图片描述

    std::vector<std::vector<int>> res;
    std::vector<int> path;
    void backtracking(std::vector<int>& nums, std::vector<bool> used){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++){
        	// used[i - 1] == false，说明同一树层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;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res.clear();
        path.clear();
        std::sort(nums.begin(), nums.end());
        std::vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }

时间复杂度: O(n! * n)；空间复杂度: O(n)

14.回溯算法去重问题的另外一个写法

子集||：在使用std::unordered_set实现去重，正确的做法是，在for循环前，创建一个set去存储在for遍历同一层节点时出现过的元素。这样就算进入下一层的递归，也能保证本层的used不受影响。
1.错误的做法一：将set定义在类成员位置（相当于全局变量），然后模拟回溯的样子 insert一次，erase一次，不是单纯地控制某一节点下的同一层了，这样就是控制整棵树，包括树枝。
2.错误做法二：把 unordered_set uset; 放到类成员位置，然后每次进入单层的时候用uset.clear()。uset已经是全局变量，本层的uset记录了一个元素，然后进入下一层之后这个uset（和上一层是同一个uset）就被清空了（backtracking()），也就是说，层与层之间的uset是同一个，那么就会相互影响

组合总和||，全排列 II：在使用std::unordered_set实现去重，正确的做法是，在for循环前，创建一个set去存储在for遍历同一层节点时出现过的元素；或者使用used布尔值数组+排序的方式实现去重。使用set去重的版本相对于used数组的版本效率都要低很多。因为回溯的过程需要频繁对set insert，然后unordered_set需要做哈希映射，这相对耗时间，而使用used数组在时间复杂度上几乎没有额外负担！

15.重新安排行程

（题目链接）
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。题目有点抽象，说明：
1.如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
2.所有的机场都用三个大写字母表示（机场代码）
3.假定所有机票至少存在一种合理的行程。
4.所有的机票必须都用一次且只能用一次。
在这里插入图片描述
这题难度很大！有点像图论里深度优先搜索的味道，亦可用回溯的方法解决。题目的难点有：

一个行程中，如果航班处理不好容易变成一个圈，成为死循环?
出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。
有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢？
== 一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场==，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map 或者std::multimap 或者 std::multiset。这样存放映射关系可以定义为 unordered_map<string, multiset<string>> targets 或者 unordered_map<string, map<string, int>> targets。在搜索过程要不断的删multiset里的元素，那么推荐使用unordered_map<string, map<string, int>> targets。在遍历unordered_map<出发机场, map<到达机场, 航班次数>> targets 的过程中，使用”航班次数“这个字段的数字做相应的增减，来标记到达机场是否使用过了。如果”航班次数“大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了。-就是不对该机场作操作而是标记一下。可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。
使用回溯法（也可以说深搜）的话，那么终止条件是什么呢？
递归函数参数和返回值：参数传入int ticketNum航班数量, std::vector<string>& result结果容器，递归函数返回bool值，因为这题相当于找到一条合适的通路通向叶子节点，使得机场能连贯起来。
终止条件：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程
单层递归的逻辑：

    std::unordered_map<std::string, std::map<std::string, int>> targets;
    bool backtracking(std::vector<std::string>& res, int ticknum){
        if(res.size()==ticknum+1) return true;
        for(std::pair<const std::string, int>& target : targets[res[res.size()-1]]){
            if(target.second>0){
                res.push_back(target.first);
                target.second--;
                if(backtracking(res, ticknum)) return true;
                target.second++;
                res.pop_back();
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        std::vector<std::string> res;
        for(const std::vector<std::string>& vec: tickets){
            targets[vec[0]][vec[1]]++;
        }
        res.push_back("JFK");
        backtracking(res, tickets.size());
        return res;
    }

16.N皇后

（题目链接）
与之前一维数组的子集，排列问题不同，这次处理的是二维棋盘问题。

    std::vector<std::vector<std::string>> res;
    void backtracking(int n, int row, std::vector<std::string>& chessboard){
        if(row==n){
            res.push_back(chessboard);
            return;
        }
        for(int i=0; i<n; i++){
            if(isVaild(n, row, i, chessboard)){
                chessboard[row][i]='Q';
                backtracking(n, row+1, chessboard);
                chessboard[row][i]='.';
            }
        }
    }
    bool isVaild(int n, int row, int col, std::vector<std::string>& chessboard){
        // 检查同一列
        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<n; i--, j++){
            if(chessboard[i][j]=='Q') return false;
        }
        // 检查135°角
        for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--){
            if(chessboard[i][j]=='Q') return false;
        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        res.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return res;
    }

17.解数独
（题目链接）
题目跟定一个有std::vector<std::vector>& board 三维带有1~9数字以及“."的9x9二维矩阵，我们需要就该矩阵完成数独的求解，并补充完成该矩阵。
递归函数从参数和返回值：找到根节点到叶子节点一条唯一的路径，需要bool返回值，输入参数则是二维矩阵
终止条件：不需要终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。但不会陷入死循环嘛？
单层递归逻辑：两层for循环分别遍历row，col，然后在使用一个for循环，填充"1"~"9"的字符，并在填入该字符前也是需要经过isVaild函数判断该位置是否有效，若有效则返回true，否则当填充字符的for循环结束后，还没找到合适的字符，则返回false。
isVaild函数：判断所在row，col上，k字符是否是独立存在的。

    bool backtacking(std::vector<std::vector<char>>& board){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.') continue;
                for(char k='1'; k<='9'; k++){
                    if(isVaild(i, j, k, board)){
                        board[i][j]=k;
                        if(backtacking(board)) return true;
                        board[i][j]='.';
                    }
                }
                return false;

            }
        }
        return true;
    }

    bool isVaild(int row, int col, char val, std::vector<std::vector<char>>& board){
        // 检查行
        for(int i=0; i<9; i++){
            if(board[row][i]==val) return false;
        }
        // 检查列
        for(int i=0; i<9; i++){
            if(board[i][col]==val) 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]==val) return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtacking(board);
    }

注意isvaild函数里关于9宫格里数字重复的判断的初始行，初始列如何计算获取的

总结

去重方式的不同

sort排序+使用used布尔数组：对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了——能实现得到唯一子集；
去重最核心的关键代码是，其实发现对于排列问题，这两种方式都能得到相同的结果；但树层上对前一位去重非常彻底，效率很高，而树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

// 对树层中前一位去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}
// 要对树枝前一位去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}