DFS 困难问题合集

37. 解数独
    用col, row, block来分别表示每一列/行/块是否有数i，先对所以可填入的位置做一个登记，存入board容器，如果有一层dfs可以填满所以空位置就可以return
    ，valid这里也可以用来提前结束

c++

class Solution {
public:
    bool col[9][9];
    bool row[9][9];
    bool block[3][3][9];
    bool valid;
    vector<pair<int,int>>spaces;

    void dfs(vector<vector<char>>& board, int pos){
        if(pos == spaces.size()){
            valid = true;
            return;
        }
        int i = spaces[pos].first;
        int j = spaces[pos].second;
        for(int t = 1;t <= 9; t++){
            if(!row[i][t - 1] && !col[j][t - 1] && !block[i/3][j/3][t-1] && !valid){
                board[i][j] = t + '0';
                row[i][t - 1] =  col[j][t - 1] = block[i/3][j/3][t-1] = true;
                dfs(board , pos + 1);
                row[i][t - 1] =  col[j][t - 1] = block[i/3][j/3][t-1] = false;
            }

        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        memset(col, false, sizeof(col));
        memset(col, false, sizeof(row));
        memset(col, false, sizeof(block));
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    auto p = make_pair(i, j);
                    spaces.push_back(p);
                }
                else{
                    row[i][board[i][j] - '0' - 1] = true;
                    col[j][board[i][j] - '0' - 1] = true;
                    block[i/3][j/3][board[i][j] - '0' - 1] = true;
                }
            }
        }
        dfs(board, 0);
    }
};

47. 全排列 II
    这道题是一道中等难度题，但这里也放到了困难，这道题对理解递归过程很好。
    最简单的思想就是先排列出所有可能的组合，再进行去重，但这复杂度很高，很多递归分支是没有必要的。比如我们开始搜索到第i个位置，有两个重复的1，在这里选这两个1的效果是一样的就可以剪枝，所以对于重复的数我们只选择一次，这个通过先对数组排序再进行判断后一个和前面的相等就可以跳过即可.
    我们还要标记一下使用过得元素防止重复使用

c++

class Solution {
public:
    vector<vector<int>>res;
    void dfs(vector<int>& cur, vector<int>& nums, vector<int>& used){
        if(cur.size() == nums.size()){
            res.push_back(cur);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0){
               continue;
            }
            if(used[i] == 0){
                used[i] = 1;
                cur.push_back(nums[i]);
                dfs(cur, nums, used);
                cur.pop_back();
                used[i] = 0;
            }    
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> used(n);
        vector<int>cur;
        dfs(cur, nums, used);
        return res;
    }
};