回溯算法（3）：番外篇

前言

我分别在回溯算法（1）：子集问题以及回溯算法（2）：全排列问题中讲解了使用回溯算法解决子集问题与全排列问题的基本思想。但是为了建立知识体系，我只选取了比较相关的方法，并将两者联系起来。
实际上这两种问题还有其他的方法解决，当然也是基于回溯算法的。为了不留下遗憾，我在这里给大家把剩下的几种方法补充一下。
注意：对于新手朋友，还是尽可能的看我前两篇文章，不然容易学得一个四不像。

子集问题的第二种解法

子集-力扣
这里我就不复述问题了，我们直接讲解思路：
对于vector<int> nums({1, 2, 3});我们不妨这样想：每个元素都有被选择与不被选择两种状态，因此我们可以构建一个完全二叉子集树如下图所示：

从头到尾遍历元素，每个元素对应有被选中（绿色）与没被选中（红色）两种状态。树的深度等于元素个数n+1。我们需要的子集就是二叉树的叶子节点。
实际上，这种方法比我在前面文章中讲的方法要更加容易理解，但之所以我没讲解这种方法主要是因为这种方法的无法应对那些比较复杂的情况，例如去重，或者是一些变形题目（可以应对但是特别困难）。此外这个方法无法与全排列建立联系，很难构建成体系。

完整代码：

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    
    void fun(int indx, vector<int>& nums) {
        if(indx == nums.size()) {
            res.push_back(path);
            return;
        }
		// 第indx个元素没有被选中，对应左侧，不需要向path中push_back
        fun(indx + 1, nums);
		// 第indx个元素被选中，对应右侧，调用push_back向path中推入元素
        path.push_back(nums[indx]); 
        fun(indx + 1, nums);
        path.pop_back();
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        fun(0, nums);
        return res;
    }
};

全排列问题的第二种解法

全排列-力扣
我之前讲过，想解决全排列问题有两个方法，时间复杂度与画出的树的结构都基本一致，分别为：
（1）元素交换法
（2）状态标注法
之前我讲的是状态标注法，进入我们要补充的就是元素交换法，直接看图：

每个节点上面的数组是继承自父节点的数组顺序，下面的数组是处理后的数组顺序，红色加粗的数字发生了位置互换。
indx = 1：第一个元素依次与自己以及后面的元素互换位置
indx = 2：第二个元素依次与自己以及后面的元素互换位置
。。。
可以看到两种方法得到的全排列树的结构基本一致，且都是取叶子节点作为结果。

完整代码：

class Solution {
    vector<vector<int>> res;
    // vector<int> path; 叫唤发不需要path，直接在nums上操作

    void fun(int indx, vector<int>& nums) 
    {
        if(indx == nums.size()) {
            res.push_back(nums);
        }

        for(int i = indx; i<nums.size(); i++) {
            swap(nums[indx], nums[i]);
            fun(indx+1, nums);
            swap(nums[indx], nums[i]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        fun(0, nums);
        return res;
    }
};

数独

数独-力扣
如果大家能做出这道题，那么基本就出师了。

class Solution {
    bool valid(vector<vector<char>>& board, int x, int y, int v) {
        for(int i = 0; i<9; i++) {
            if(v == board[i][y] || v == board[x][i]) return false;
        }
        int areax = x/3;
        int areay = y/3;
        for(int i = 0; i < 9; i++) {
            int dx = i%3;
            int dy = i/3;
            if(v == board[dx+areax*3][dy+areay*3]) return false;
        }
        return true;
    }

    bool fun(int indx, vector<vector<char>>& board) {
        if(indx > 80) return true;
        int x = indx%9;
        int y = indx/9;
        if(board[x][y] == '.') {
            for(int v = 1; v <= 9; v++) {
                if(!valid(board, x, y, v + '0')) {
                    continue;
                }
                board[x][y] = v + '0';
                if(fun(indx+1, board)) { return true; }
                board[x][y] = '.';
            }
        }
        else {
            return fun(indx+1, board);
        }
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        fun(0, board);
        return;
    }
};