题解

  • 22 Generate Parentheses
    • Patch result only when valid parentheses sequence.
  • 37 Sudoku Solver
    • Patch result only when valid sudoku.

51 N queues

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> path(n, string(n, '.'));
        vector<vector<string>> result;
        vector<bool> col(n, false);
        vector<bool> rightdown(2*n-1, false);
        vector<bool> leftup(2*n-1, false);

        dfs(path, result, col, rightdown, leftup, 0, n);

        return result;
    }

    void dfs(vector<string>& path, vector<vector<string>>& result, vector<bool>& col, vector<bool>& rightdown, vector<bool>& leftup, int row, int n) {
        if (row == n) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (col[i] == true) continue;
            if (rightdown[n-1+row-i] == true) continue;
            if (leftup[row+i] == true) continue;

            col[i] = true;
            rightdown[n-1+row-i] = true;
            leftup[row+i] = true;
            path[row][i] = 'Q';
            dfs(path, result, col, rightdown, leftup, row+1, n);
            path[row][i] = '.';
            leftup[row+i] = false;
            rightdown[n-1+row-i] = false;
            col[i] = false;
        }
    }
};

39 Combination Sum

  • Numbers w/o duplicate. DFS monoly on set.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        vector<vector<int>> result;

        dfs(candidates, path, result, 0, target);

        return result;

    }

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, int l, int target) {
        if (target == 0) {
            result.push_back(path);
            return;
        }

        for (int i = l; i < nums.size(); i++) {
            if (nums[i] > target) continue;
            path.push_back(nums[i]);
            dfs(nums, path, result, i, target-nums[i]);
            path.pop_back();
        }
    }
};

40 Combination Sum II

  • Numbers with duplicate. DFS monoly on sorted set, and skip duplicates before patching.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> path;
        vector<vector<int>> result;
        vector<bool> used(candidates.size(), false);

        sort(candidates.begin(), candidates.end());
        dfs(candidates, path, result, 0, target, used);

        return result;

    }

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, int l, int target, vector<bool>& used) {
        if (target == 0) {
            result.push_back(path);
            return;
        }

        for (int i = l; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) {
                continue;
            }

            if (nums[i] > target) continue;
            path.push_back(nums[i]);
            used[i] = true;
            dfs(nums, path, result, i+1, target-nums[i], used);
            path.pop_back();
            used[i] = false;
        }
    }
};

46 Permutations

  • Numbers w/o duplicate. At each level try all numbers.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<vector<int>> result;
        vector<bool> used(nums.size(), false);

        dfs(nums, path, result, used);

        return result;
    }

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;

            path.push_back(nums[i]);
            used[i] = true;
            dfs(nums, path, result, used);
            used[i] = false;
            path.pop_back();
        }
    }
};

47 Permutations II

  • Numbers with duplicate. DFS on sorted set, and skip duplicates.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> path;
        vector<vector<int>> result;
        vector<bool> used(nums.size(), false);

        sort(nums.begin(), nums.end());
        dfs(nums, path, result, used);

        return result;
    }

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;

            path.push_back(nums[i]);
            used[i] = true;
            dfs(nums, path, result, used);
            used[i] = false;
            path.pop_back();
        }
    }

};
  • 60 Permutation Sequence
    • Generate k-th permutation of 1…n.
    • O(n^2) time, enumerate digits from the most siginificant position.
    • O(nlog(n)) time if using BST or BIT to support log(n) looking up and updating for i-th digit.

77 Combinations

  • Numbers w/o duplicate, generate (n, k) results. DFS monoly on sorted set.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        vector<vector<int>> result;

        dfs(path, result, 1, n, k);

        return result;
    }

    void dfs(vector<int>& path, vector<vector<int>>& result, int l, int n, int k) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        for (int i = l; i <= n; i++) {
            path.push_back(i);
            dfs(path, result, i+1, n, k);
            path.pop_back();
        }
    }
};

78 Subsets

  • Numbers w/o duplicate. DFS monoly on sorted set and add to result at each level.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;

        dfs(nums, path, result, 0);

        return result;
    }

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, int l) {
        result.push_back(path);
        for (int i = l; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, path, result, i+1);
            path.pop_back();
        }
    }

};
  • 89 Gray Code
    • Gray code encodes 1 to n with 1 to n but each adjacent pair differs only in 1 bit.
    • Note that the gray codes can be divided into parts with most significants 1 or 0.

90 Subsets II

  • Numbers with duplicate, generate (n, k) results. Solutions must not duplicate. Skip duplicates before patching.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);

        sort(nums.begin(), nums.end());
        dfs(nums, path, result, 0, used);

        return result;
    }

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& paths, int l, vector<bool>& used) 		{
        paths.push_back(path);
        for (int i = l; 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;
            dfs(nums, path, paths, i+1, used);
            used[i] = false;
            path.pop_back();
        }
    }
};
  • Given a letter grid, search for target word’s path. Brute-force DFS.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    //cout << "new search" << endl;
                    bool existed = dfs(board, word, visited, i, j, 1);
                    if (existed) return true;
                }
            }
        }

        return false;
    }

    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    bool inBoard(vector<vector<char>>& board, int x, int y) {
        int m = board.size();
        int n = board[0].size();

        return x >= 0 && y >= 0 && x < m && y < n;
    }

    bool dfs(vector<vector<char>>& board, string word, vector<vector<bool>>& visited, int row, int col, int index) {
        if (index == word.size()) {
            return true;
        }

        visited[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int x = row + dir[i][0];
            int y = col + dir[i][1];

            if (inBoard(board, x, y) && !visited[x][y] && board[x][y] == word[index]) {
                //cout << "search " << x << ' ' << y << ' ' << index << endl;
                visited[x][y] = true;
                bool existed = dfs(board, word, visited, x, y, index+1);
                if (existed) return true;
                visited[x][y] = false;
            }
        }

        visited[row][col] = false;
        return false;
    }
};
  • 93 Restore IP Addresses
    • Given a digit string, split it into valid IP.
  • 131 Palindrome Partitioning
    • Given a string, return all palindrome partitions. Test whether palindrome before DFS.
  • 216 Combination Sum III
    • Numbers in 1-9 and exactly k numbers, w/o duplicate. DFS monoly, and return when there is not enough numbers.
  • 254 Factor Combinations
    • Given a number, generate all factor decompositions of it. First generate all factors and DFS on them. Can use “Humble Number” alike method to accelerate it.
  • 267 Palindrome Permutation II
    • Given a string, generate all its permutaions that are palindrome. Simple letter count.
  • 291 Word Pattern II
    • Given a pattern string like “abab” and a target string like “xxyyxxyy”, find if there is a bijection between pattern string’s single characters and target string’s non-empty segments.
    • Enumerate possible segments for each character and memo enumerated results.
  • 306 Additive Number
    • Given a string, find whether it can be parsed as a fibonacci sequence.
    • Enumerate start state and validate following states.
  • 320 Generalized Abbreviation
    • Given a word, generate its generalized abbreviations, e.g., “word”: “w1rd”, “w2d”, “3w”, “4”, etc.
    • DP or bit manipulation also work.
  • 351 Android Unlock Patterns
    • Calculate number of k-length Android unlock patterns.
    • DFS, reuse symmetric cases.

参考资料