DFS题目

组合

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

• 写法一：获取当前vec的最后一个数作为基准开始遍历

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector vec {0}; // 先存一个0作为基准，因为dfs从当前vec的最后一个数+1开始遍历
        function<void(void)> dfs = [&]() {  // lambda函数，不用在外部定义了
            if (size(vec) == k + 1) {
                res.emplace_back(begin(vec)+1, end(vec));
                //push_back()占内存且浪费时间
                return ;
            } 
            for (int i = vec.back() + 1; i - size(vec) + k <= n ; ++i) {
                vec.push_back(i);
                dfs();
                vec.pop_back();
            }
        };
        dfs();
        return res;
    }
};

• 写法二：

class Solution {
public:
    vector<vector<int>> res;
    void dfs(vector<int> &vec, int idx, int n, int k) {
        if (vec.size() + (n - idx + 1) < k) return ;  

        if (vec.size() == k) {
            res.push_back(vec);
            return ;
        }
		// 两个dfs，一个是选择当前idx，一个是不选择当前idx
        vec.push_back(idx);
        dfs(vec, idx + 1, n, k);
        vec.pop_back();
        dfs(vec, idx + 1, n, k);

    }
    vector<vector<int>> combine(int n, int k) {
        if (!n) return res;
        vector<int> vec;
        dfs(vec, 1, n, k);
        return res;
    }
};

子集

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

第一层进入枚举所有的范围，并且每次递归的cur都是答案，在下层的递归中减少左端范围，自然的将已选择的数排除。

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur;
    int n = size(nums);
    function<void(int)> dfs = [&](int idx) {
        res.emplace_back(cur);// 
        for (int i = idx + 1; i < n; ++ i) {
            cur.emplace_back(nums[i]);
            dfs(i );
            cur.pop_back();
        }
    };
    dfs(-1);
    return res;
}

解数独

class Solution {
public:
    const int N = 9;
    vector<bitset<9>> rows;
    vector<bitset<9>> cols;
    vector<bitset<9>> cells;
    void mask(int x, int y, int num, bool flag) {
        rows[x][num] = flag ? 1 : 0;
        cols[y][num] = flag ? 1 : 0;
        cells[x/3*3 + y/3][num] = flag ? 1 : 0;
    }

    bitset<9> getStatus(int x, int y) {
        return ~(rows[x] | cols[y] | cells[x/3*3 + y/3]);
    }

    vector<int> getNext(vector<vector<char>> &board) {
        vector<int> coord;
        int useNum = 10;
        // 返回一个可填充数量最少的坐标 
        for (int i = 0; i < N; ++ i) {
            for (int j = 0; j < N; ++ j) {
                if (board[i][j] == '.') {
                    auto useable = getStatus(i, j);
                    if (useable.count() < useNum) {
                        useNum = useable.count();
                        coord = {i, j};
                    }
                }
            }
        }
        return coord;
    }

    bool dfs(vector<vector<char>>& board, int cnt) {
        if (cnt == 0) return true;
        auto coord = getNext(board);
        auto useable = getStatus(coord[0], coord[1]);
        for (int i = 0; i < N; ++ i) { // 遍历9个数字
            if (!useable[i]) continue;
            mask(coord[0], coord[1], i, true);
            board[coord[0]][coord[1]] = i + '1';
            if (dfs(board, cnt - 1)) return true;
            mask(coord[0], coord[1], i, false);
            board[coord[0]][coord[1]] = '.';
        }
        return false;
    }

    void solveSudoku(vector<vector<char>>& board) 
    {
        rows = vector<bitset<9>>(9, bitset<9>());
        cols = vector<bitset<9>>(9, bitset<9>());
        cells = vector<bitset<9>>(9, bitset<9>());

        int cnt = 0;
        for (int i = 0; i < N; ++ i) {
            for (int j = 0; j < N; ++ j) {
                if (board[i][j] == '.'){
                    ++ cnt;
                    continue;
                }
                mask(i, j, board[i][j]-'1', true);
            }
        }
        dfs(board, cnt);
    }
};