LeetCode Hot100 Backtrace

Posted on Edited on

全排列

Problem

https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索

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<int>> ans;
    void dfs(const vector<int> &nums, int depth, vector<bool> &flag, vector<int> &temp_ans)
    {
        if (depth == nums.size())
        {
            ans.push_back(temp_ans);
            return;
        }
        else
        {
            for (int i = 0; i < nums.size(); i ++)
            {
                if (!flag[i])
                {
                    flag[i] = true;
                    temp_ans.push_back(nums[i]);
                    dfs(nums, depth+1, flag, temp_ans);
                    temp_ans.pop_back();
                    flag[i] = false;
                }
            }
        }
        return;
    }

    vector<vector<int>> permute(vector<int>& nums) {

        vector<bool> flag(nums.size(), false);
        vector<int> temp_ans;

        dfs(nums, 0, flag, temp_ans);

        return ans;
    }
};

子集

Problem

https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked

Solution

每个元素都有出现与不出现两种可能，深度优先搜索枚举所有情况。

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>> ans;
    void dfs(const vector<int> &nums, int depth, vector<int> &temp_ans)
    {
        if (depth == nums.size())
        {
            ans.push_back(temp_ans);
            return;
        }

        dfs(nums, depth+1, temp_ans);
        temp_ans.push_back(nums[depth]);
        dfs(nums, depth+1, temp_ans);
        temp_ans.pop_back();
        return;
    }
    vector<vector<int>> subsets(vector<int>& nums) {

        vector<int> temp_ans;

        dfs(nums, 0, temp_ans);

        return ans;
    }
};

电话号码的字母组合

Problem

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索

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:

    string num2str[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans;

    void dfs(const string &digits, int depth, string &temp_ans)
    {
        if (depth == digits.size())
        {
            ans.push_back(temp_ans);
            return;
        }

        for (char ch : num2str[digits[depth]-'2'])
        {
            temp_ans.push_back(ch);
            dfs(digits, depth+1, temp_ans);
            temp_ans.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return {};
        string temp_ans;
        dfs(digits, 0, temp_ans);
        return ans;
    }
};

组合总和

Problem

https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索，每次从集合中选择一个数，由于可重复，所以这次选完之后，下次选择的范围是从这个数开始。枚举所有情况即可。

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>> ans;
    int target_;

    void dfs(const vector<int> &candidates, int start, vector<int> &temp_ans, int temp_sum)
    {
        if (temp_sum == target_)
        {
            ans.push_back(temp_ans);
            return;
        }

        if (temp_sum > target_) return;

        for (int i = start; i < candidates.size(); i ++)
        {
            temp_ans.push_back(candidates[i]);
            dfs(candidates, i, temp_ans, temp_sum+candidates[i]);
            temp_ans.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        target_ = target;
        vector<int> temp_ans;
        dfs(candidates, 0, temp_ans, 0);
        return ans;
    }
};

括号生成

Problem

https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索，每次可以选择添加左括号也可以选择添加右括号，枚举所有情况，剪枝掉不合法的情况。

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
class Solution {
public:

    vector<string> ans;

    void dfs(int n, int left_num, int right_num, string &temp_ans)
    {
        if (n == left_num && n == right_num)
        {
            ans.push_back(temp_ans);
            return;
        }
        if (left_num < right_num) return;
        if (left_num > n) return;
        temp_ans.push_back('(');
        dfs(n, left_num+1, right_num, temp_ans);
        temp_ans.back() = ')';
        dfs(n, left_num, right_num+1, temp_ans);
        temp_ans.pop_back();
    }

    vector<string> generateParenthesis(int n) {
        string temp_ans = "";
        dfs(n, 0, 0, temp_ans);
        return ans;
    }
};

单词搜索

Problem

https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked

Solution

首先遍历board，找到word[0]，从它开始深度优先搜索依次找word[idx]直到word内字母全部找到，设置visited数组防止重复走。

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
52
class Solution {
public:
    int m;
    int n;
    vector<vector<bool>> visited;

    bool dfs(const vector<vector<char>> &board, int i, int j, const string &word, int idx)
    {
        if (idx >= word.size())
        {
            return true;
        }
        bool ret = false;
        for (int x = 0; x < 4; x ++)
        {
            int xi = i + (x < 2 ? x % 2 ? -1 : 1 : 0);
            int xj = j + (x < 2 ? 0 : x % 2 ? -1 : 1);

            if (xi >= 0 && xi < m && xj >= 0 && xj < n)
            {
                if (!visited[xi][xj] && word[idx] == board[xi][xj])
                {
                    visited[xi][xj] = true;
                    ret |= dfs(board, xi, xj, word, idx+1);
                    visited[xi][xj] = false;
                }
            }
        }
        return ret;
    }

    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();

        visited = vector<vector<bool>>(m, vector<bool>(n, false));
        bool ans = false;
        for (int i = 0; i < m; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (board[i][j] == word[0] && !visited[i][j])
                {
                    visited[i][j] = true;
                    ans |= dfs(board, i, j, word, 1);
                    visited[i][j] = false;
                }
            }
        }
        return ans;
    }
};

分割回文串

Problem

https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked

Solution

提前算好回文串dp，深度优先搜索枚举所有截取子串的方式，把不是回文串的情况剪枝剪掉。
要注意初始化dp的时候默认设为true。

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
class Solution {
public:

    vector<vector<string>> ans;
    vector<vector<bool>> dp;
    int n;

    void dfs(const string &s, int start, vector<string> &temp_ans)
    {
        if (start == n)
        {
            ans.push_back(temp_ans);
            return;
        }

        for (int end = start; end < n; end ++)
        {
            if (dp[start][end])
            {
                temp_ans.push_back(s.substr(start, end-start+1));
                dfs(s, end+1, temp_ans);
                temp_ans.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        dp = vector<vector<bool>>(n, vector<bool>(n, true));

        for (int len = 1; len <= n; len ++)
        {
            for (int start = 0; start < n-len+1; start ++)
            {
                int end = start + len - 1;
                dp[start][end] = (len == 1) ? true : (dp[start+1][end-1] && s[start] == s[end]);
            }
        }
        vector<string> temp_ans;
        dfs(s, 0, temp_ans);
        return ans;
    }
};

N皇后

Problem

https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索，每次选择将皇后放在这一行的哪一列，需要按照规则判断一下，如果这个位置可以放，就放这里，然后选下一行的位置。

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
52
53
54
55
56
57
58
class Solution {
public:
    int n_;
    vector<vector<string>> ans;

    bool can_set(const vector<string> &temp_ans, int row, int col)
    {
        for (int i = 0; i < row; i ++)
        {
            if (temp_ans[i][col] == 'Q')
                return false;
        }

        for (int x = 1; row-x >= 0 && (col-x >= 0 || col + x < n_); x ++)
        {
            if (col-x >= 0)
            {
                if (temp_ans[row-x][col-x] == 'Q')
                    return false;
            }

            if (col+x < n_)
            {
                if (temp_ans[row-x][col+x] == 'Q')
                    return false;
            }
        }
        return true;
    }

    void dfs(vector<string> &temp_ans, int row)
    {
        if (row == n_)
        {
            ans.push_back(temp_ans);
            return;
        }

        for (int col = 0; col < n_; col ++)
        {
            if (can_set(temp_ans, row, col))
            {
                temp_ans[row][col] = 'Q';
                dfs(temp_ans, row+1);
                temp_ans[row][col] = '.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        n_ = n;
        string row_str = string(n, '.');
        vector<string> temp_ans(n, row_str);

        dfs(temp_ans, 0);
        return ans;
    }
};