回溯算法框架

  1. 回溯算法实质上是一种暴力穷举算法
  2. 穷举的过程就是遍历一颗多叉树的过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
List<Value> ans;
void dfs(路径, 选择列表) {
		if (满足结束条件) {
				ans.add(路径);
				return ;
		}
		for (选择 : 选择列表) {
				做选择;
				dfs(路径,  选择列表);
				撤销选择;
		}
}

// 多叉树遍历框架
void dfs(TreeNode root) {
		if (root == null) {
				return ;
		}
		for (TreeNode child : root.children) {
				dfs(child);
		}
}

回溯三问：思考回溯问题的套路

  1. 当前操作？枚举path[i]要填入的字母
  2. 子问题？构造字符串 ≥i 的部分
  3. 下一个子问题？构造字符串 ≥ i + 1 的部分

dfs(i) → dfs(i + 1)

dfs(i) 表示 ≥ i 的数，而不是下标 i 的数

从多重循环到回溯

回溯有一个增量构造答案的过程，这个过程通常用递归实现。递归确定好边界条件和非边界条件。

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。
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 {
    final String[] MAPPING = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> ans;
    char[] path;
    String digits;

    public List<String> letterCombinations(String digits) {
        ans = new ArrayList<String>();
        if (digits.length() == 0) {
            return ans;
        }
        path = new char[digits.length()];
        this.digits = digits;
        dfs(0);
        return ans;
    }

    void dfs(int i) {
        if (i == digits.length()) {
            ans.add(new String(path));
            return ;
        }
        for (char c : MAPPING[digits.charAt(i) - '0'].toCharArray()) {
            path[i] = c;
            dfs(i + 1);
        }
    }
}

子集型回溯

每个元素都可以选/不选

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10

  • 10 <= nums[i] <= 10

  • nums 中的所有元素 互不相同

  • 回溯三问（方法一）

    1. 当前操作？枚举第 i 个数选/不选
    2. 子问题？从下标 ≥ i 的数字中构造子集
    3. 下一个子问题？从下标 ≥ i + 1 的数字中构造子集

    dfs(i) → dfs(i + 1)

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 {
    List<List<Integer>> ans;
    Stack<Integer> st;
    int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        ans = new ArrayList<List<Integer>>();
        st = new Stack<Integer>();
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<Integer>(st));
            return ;
        }
        st.add(nums[i]);    // 选当前的数
        dfs(i + 1);
        st.pop();   // 不选当前的数，也叫恢复现场
        dfs(i + 1);
    }
}

/* 
 * [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
 */

  • 回溯三问（方法二）

    1. 当前操作？枚举一个下标 j ≥ i 的数组，加入 path
    2. 子问题？从下标 ≥ i 的数字中构造子集
    3. 下一个子问题？从下标 ≥ j + 1 的数字中构造子集

    Untitled

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 {
    List<List<Integer>> ans;
    Stack<Integer> st;
    int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        ans = new ArrayList<List<Integer>>();
        st = new Stack<Integer>();
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        ans.add(new ArrayList(st));
        for (; i < nums.length; ++i) {
            st.push(nums[i]);
            dfs(i + 1);
            st.pop();
        }
    }
}

/*
 * [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
 */

131. 分割回文串

给你一个字符串 s，请你将 **s **分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

方法一：答案的视角（枚举子串结束位置）

  • 回溯三问

    1. 当前操作？选择回文子串 s[i..j]，加入path
    2. 子问题？从下标 ≥ i 的后缀中构造回文分割
    3. 下一个子问题？从下标 ≥ j + 1 的后缀中构造回文分割

    Untitled

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
class Solution {
    List<List<String>> ans;
    Stack<String> path;
    String s;

    public List<List<String>> partition(String s) {
        ans = new ArrayList<List<String>>();
        path = new Stack<String>();
        this.s = s;
        dfs(0);
        return ans;
    }
    void dfs(int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<String>(path));
            return ;
        }
        for (int j = i; j < s.length(); ++j) {
            if (isPalindrome(i, j)) {   // isPalindrome 是闭区间，substring 是左闭右开区间
                path.push(s.substring(i, j + 1));
                dfs(j + 1);
                path.pop();
            }
        }
    }

    boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

// aabb
// [["a","a","b","b"],["a","a","bb"],["aa","b","b"],["aa","bb"]]

方法二：输入的视角（逗号选或不选）

  • 回溯三问

    1. 当前操作？枚举第 i 个数选/不选
    2. 子问题？从下标 ≥ i 的数字中构造子集
    3. 下一个子问题？从下标 ≥ i + 1 的数字中构造子集

    dfs(i) → dfs(i + 1)

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
class Solution {
    List<List<String>> ans = new ArrayList<List<String>>();
    Stack<String> path = new Stack<String>();
    String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0, 0);
        return ans;
    }

    // start means the start of the substring
    void dfs(int i, int start) {
        // [start, i]
        if (i == s.length()) {
            ans.add(new ArrayList<String>(path));
            return ;
        }
        // not choose the comma between i and i + 1
        if (i < s.length() - 1) {
            // [start, i + 1]
            dfs(i + 1, start);
        }
        // choose the comma that only the method isPalindrome returned true between i and i + 1
        if (isPalindrome(start, i)) {
            // [start, i]
            path.push(s.substring(start, i + 1));
            // [i + 1, i + 1]
            dfs(i + 1, i + 1);
            // restore the scene
            path.pop();
        }
    }

    boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
// aabb
// [["aa","bb"],["aa","b","b"],["a","a","bb"],["a","a","b","b"]]

784. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：

1
2
输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:

1
2
输入: s = "3z4"
输出: ["3z4","3Z4"]

提示:

  • 1 <= s.length <= 12
  • s 由小写英文字母、大写英文字母和数字组成
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
class Solution {
    List<String> ans;
    char[] path;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList<String>();
        path = s.toCharArray();
        dfs(0);
        return ans;
    }

    void dfs(int i) {
        if (i == path.length) {
            ans.add(new String(path));
            return ;
        }
        if (Character.isLetter(path[i])) {
            // a ^= 32 -> A, A ^= 32 -> a
            // 转换大小写
            path[i] ^= 32;   
            dfs(i + 1);
            path[i] ^= 32;
        }
        dfs(i + 1);
    }
}

1601. 最多可达成的换楼请求数目（未掌握）

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。

给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。

一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。

请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

示例 1：

https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/26/move1.jpg

1
2
3
4
5
6
7
8
9
10
11
输入：n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出：5
解释：请求列表如下：
从楼 0 离开的员工为 x 和 y ，且他们都想要搬到楼 1 。
从楼 1 离开的员工为 a 和 b ，且他们分别想要搬到楼 2 和 0 。
从楼 2 离开的员工为 z ，且他想要搬到楼 0 。
从楼 3 离开的员工为 c ，且他想要搬到楼 4 。
没有员工从楼 4 离开。
我们可以让 x 和 b 交换他们的楼，以满足他们的请求。
我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。
所以最多可以满足 5 个请求。

示例 2：

https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/26/move2.jpg

1
2
3
4
5
6
7
输入：n = 3, requests = [[0,0],[1,2],[2,1]]
输出：3
解释：请求列表如下：
从楼 0 离开的员工为 x ，且他想要回到原来的楼 0 。
从楼 1 离开的员工为 y ，且他想要搬到楼 2 。
从楼 2 离开的员工为 z ，且他想要搬到楼 1 。
我们可以满足所有的请求。

示例 3：

1
2
输入：n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出：4

提示：

  • 1 <= n <= 20
  • 1 <= requests.length <= 16
  • requests[i].length == 2
  • 0 <= fromi, toi < n
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
class Solution {
    int[][] requests;
    int[] delta;    // count employee changes 
    int ans = 0, cnt = 0, zero, n;
    // recall + enumerate
    public int maximumRequests(int n, int[][] requests) {
        delta = new int[n];
        zero = n;   // count the val of 0 in delta
        this.n = n;
        this.requests = requests;
        // start from the first requests
        dfs(0);
        return ans;
    }

    void dfs(int i) {
        if (i == requests.length) {
            if (zero == n) {
                ans = Math.max(ans, cnt);
            }
            return ;
        }
        // not choose requests[i]
        dfs(i + 1);
        // choose requests[i]
        int z = zero;
        ++cnt;
        int x = requests[i][0], y = requests[i][1];
        zero -= delta[x] == 0 ? 1 : 0;
        --delta[x];
        zero += delta[x] == 0 ? 1 : 0;
        zero -= delta[y] == 0 ? 1 : 0;
        ++delta[y];
        zero += delta[y] == 0 ? 1 : 0;
        dfs(i + 1);
        --delta[y]; 
        ++delta[x];
        --cnt;
        // restore the scene
        zero = z;
    } 
}

2397. 被列覆盖的最多行数（未掌握）

给你一个下标从 0 开始的 m x n 二进制矩阵 mat 和一个整数 cols ，表示你需要选出的列数。

如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行 被覆盖 了。

请你返回在选择 cols 列的情况下，被覆盖 的行数 最大 为多少。

示例 1：

https://assets.leetcode.com/uploads/2022/07/14/rowscovered.png

1
2
3
4
5
输入：mat = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], cols = 2
输出：3
解释：
如上图所示，覆盖 3 行的一种可行办法是选择第 0 和第 2 列。
可以看出，不存在大于 3 行被覆盖的方案，所以我们返回 3 。

示例 2：

https://assets.leetcode.com/uploads/2022/07/14/rowscovered2.png

1
2
3
4
5
输入：mat = [[1],[0]], cols = 1
输出：2
解释：
选择唯一的一列，两行都被覆盖了，原因是整个矩阵都被覆盖了。
所以我们返回 2 。

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 12
  • mat[i][j] 要么是 0 要么是 1 。
  • 1 <= cols <= n
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 int maximumRows(int[][] mat, int cols) {
        int m = mat.length, n = mat[0].length;
        int[] mask = new int[m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mask[i] |= mat[i][j] << j;
            }
        } 
        int ans = 0, state = 1 << n;
        for (int set = 0; set < state; ++set) {
            // the count of bit if not equal, then continue
            if (Integer.bitCount(set) != cols) {
                continue;
            }
            int cnt = 0;
            for (int row : mask) {
                if ((row & set) == row) {
                    ++cnt;
                }
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

组合型回溯

  • 剪枝

    从n个数中选k个数的组合，可以看成是长度固定的子集

    设path长为m，那么还需要选d=k-m个数

    设当前需要从[1,i]这i个数中选数，如果i<d，最后必然无法选出k个数，不需要继续递归

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

方法一：枚举下一个数选哪个

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 {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Stack<Integer> path = new Stack<Integer>();
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        dfs(n); // enumerate from n to 1 have an effect that it is not necessary to preserve n
        return ans;
    }

    void dfs(int i) {
        // lopping -- to reduce the times of dfs
        int d = k - path.size();    // d represents the quantity of numbers that we can choose from 
        if (d == 0) {   // The search concludes if d = 0
            ans.add(new ArrayList<Integer>(path));
            return ;
        }
        for (int j = i; j >= d; --j) {   // lopping -- only numbers greater than d can be chosen
            // [d, i] -> i - d + 1
            path.push(j);
            dfs(j - 1);
            path.pop();
        }
    }
}

方法二：选或不选

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
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Stack<Integer> path = new Stack<Integer>();
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        dfs(n); // enumerate from n to 1 have an effect that it is not necessary to preserve n
        return ans;
    }

    void dfs(int i) {
        int d = k - path.size();
        if (d == 0) {
            ans.add(new ArrayList<Integer>(path));
            return ;
        }
        if (i > d) {
            dfs(i - 1);
        }
        path.push(i);
        dfs(i - 1);
        path.pop();
    }
}

216. 组合总和 III

找出所有相加之和为 n **的 k ****个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入:k = 3,n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入:k = 3,n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
5
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

方法一：枚举下一个数选哪个

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 {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Stack<Integer> path = new Stack<Integer>();
    int k;
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        dfs(9, n);
        return ans;
    }
    // range : [1, i], t : target
    void dfs(int i, int t) {
        int d = k - path.size();    // the amount of numbers that can be chosen is d
        // lopping
        if (t < 0 || t > (i + i - d + 1) * d / 2) {  // [a1, a2, ..., ad] the formula of sum
            return ;
        }  
        if (d == 0) {
            ans.add(new ArrayList<Integer>(path));
            return ;
        }
        for (int j = i; j >= d; --j) {
            path.add(j);
            dfs(j - 1, t - j);
            path.pop();
        }
    }
}

方法二：选或不选

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 {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Stack<Integer> path = new Stack<Integer>();
    int k;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        dfs(9, n);
        return ans;
    }

    void dfs(int i, int t) {
        int d = k - path.size();
        if (t < 0 || t > ((((i << 1) - d + 1) * d) >> 1)) {
            return ;
        }
        if (d == 0) {
            ans.add(new ArrayList<Integer>(path));
            return ;
        }
        if (i > d) {
            dfs(i - 1, t);
        }
        path.add(i);
        dfs(i - 1, t - i);
        path.pop();
    }
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1
2
输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

方法一：选左括号还是选右括号

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 {
    List<String> ans = new ArrayList<String>();
    char[] path;
    int m;
    public List<String> generateParenthesis(int n) {
        m = n << 1;
        path = new char[m];
        dfs(0, 0);
        return ans;
    }
    // i is the index of string, open is the amount of left brackets and the amount of right brackets is i - open
    void dfs(int i, int open) {
        if (i == m) {
            ans.add(new String(path));
            return ;
        }
        if (open < (m >> 1)) {  // choose the left bracket
            path[i] = '(';
            dfs(i + 1, open + 1);
        }
        if (i - open < open) {  // the amount of right brackets must less than left brackets
            path[i] = ')';
            dfs(i + 1, open);
        }
    }
}

方法二：枚举下一个左括号的位置

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 {
    List<String> ans = new ArrayList<String>();
    Stack<Integer> path = new Stack<Integer>();
    int n;
    
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0);
        return ans;
    }
    // balance = the amount of left brackets - the amount of right brackets
    void dfs(int i, int balance) {
        if (path.size() == n) {
            char[] s = new char[n << 1];
            Arrays.fill(s, ')');
            for (int j : path) {
                s[j] = '(';
            }
            ans.add(new String(s));
            return ;
        }
        // it can be filled right brackets from 0 to balance
        for (int close = 0; close <= balance; ++close) {
            path.add(i + close);   // fill one left bracket
            dfs(i + close + 1, balance - close + 1);
            path.pop();
        }
    }
}

301. 删除无效的括号（没搞懂）

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

1
2
输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

1
2
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

1
2
输入：s = ")("
输出：[""]

提示：

  • 1 <= s.length <= 25
  • s 由小写英文字母以及括号 '(' 和 ')' 组成
  • s 中至多含 20 个括号
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
class Solution {
    Set<String> ans = new HashSet<>();
    String s;
    int maxLen, len;

    public List<String> removeInvalidParentheses(String s) {
        this.s = s;
        int cntLeft = 0, cntRight = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                ++cntLeft;
            } else if (c == ')') {
                ++cntRight;
            } 
        }
        maxLen = Math.min(cntLeft, cntRight);
        dfs(0, "", 0);
        return new ArrayList<>(ans);
    }
    // i is the index of s
    // cur is the path that we choose
    // score is the balance between left and right
    void dfs(int i, String path, int score) {
        if (score < 0 || score > maxLen) {
            return ;
        }
        if (i == s.length()) {
            if (score == 0 && path.length() >= len) {
                if (path.length() > len) {  // len is the 
                    ans.clear();
                }
                len = path.length();
                ans.add(path);
            }
            return ;
        }
        char c = s.charAt(i);
        if (c == '(') {
            dfs(i + 1, path + '(', score + 1);  // choose '('
            dfs(i + 1, path, score);    // not choose '('
        } else if (c == ')') {
            dfs(i + 1, path + ')', score - 1);  // choose ')'
            dfs(i + 1, path, score);    // not choose ')'
        } else {    // other character
            dfs(i + 1, path + c, score);
        }
    }
}
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
59
class Solution {
    Set<String> ans = new HashSet<String>();
    String s;
    int maxLen, len;

    public List<String> removeInvalidParentheses(String s) {
        this.s = s;
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                ++left;
            } else if (c == ')') {
                ++right;
            }
        }
        maxLen = Math.min(left, right); // the max length of left or right brackets
        left = right = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                ++left;
            } else if (c == ')') {
                if (left != 0) {
                    --left;
                } else {
                    ++right;
                }
            }
        }
        len = s.length() - left - right;
        dfs(0, "", left, right, 0);
        return new ArrayList<String>(ans);
    }

    void dfs(int i, String cur, int left, int right, int score) {
        if (left < 0 || right < 0 || score < 0 || score > maxLen) {
            return ;
        }
        if (left == 0 && right == 0) {
            if (cur.length() == len) {
                ans.add(cur);
            }
        }
        if (i == s.length()) {
            return ;
        }
        char c = s.charAt(i);
        if (c == '(') {
            dfs(i + 1, cur + c, left, right, score + 1);
            dfs(i + 1, cur, left - 1, right, score);
        } else if (c == ')') {
            dfs(i + 1, cur + c, left, right, score - 1);
            dfs(i + 1, cur, left, right - 1, score);
        } else {
            dfs(i + 1, cur + c, left, right, score);
        }
    }
}

子集型回溯 组合型回溯 小结

方法一：选或不选

方法二：枚举选哪个

理论上两个方法都能得到答案，但有的题目更适合选或不选，有的题目更适合枚举选哪个

排列型回溯

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • 10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同
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
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Stack<Integer> path = new Stack<Integer>();
    boolean[] onPath;
    int[] nums;
    
    public List<List<Integer>> permute(int[] nums) {
        onPath = new boolean[nums.length];
        this.nums = nums;
        dfs(0);
        return ans;
    }

    void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return ;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (onPath[j]) {
                continue;
            }
            path.add(nums[j]);
            onPath[j] = true;
            dfs(i + 1);
            path.pop();
            onPath[j] = false;
        }
    }
}

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 **n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

https://assets.leetcode.com/uploads/2020/11/13/queens.jpg

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9
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
class Solution {
    List<List<String>> ans = new ArrayList<List<String>>();
    int[] column;
    // diag1 records the situation in the upper right that r + c = R + C
    // diag2 records the situation in the upper left that r - c = R - C
    boolean[] onPath, diag1, diag2;
    int n;

    List<String> generateMapping() {
        List<String> ret = new ArrayList<>();
        char[] string = new char[n];
        Arrays.fill(string, '.');
        for (int col : column) {
            string[col] = 'Q';
            ret.add(new String(string));
            string[col] = '.';
        }
        return ret;
    }

    void dfs(int row) {
        if (row == n) {
            ans.add(generateMapping());
            return ;
        }    
        for (int col = 0; col < n; ++col) {
            // "row - col + n - 1" : n - 1 is to prevent the minus number
            if (!onPath[col] && !diag1[row + col] && !diag2[row - col + n - 1]) {
                column[row] = col;
                onPath[col] = diag1[row + col] = diag2[row - col + n - 1] = true;
                dfs(row + 1);
                onPath[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        column = new int[n];
        onPath = new boolean[n];
        // both the max index of row and column are n - 1, so the range is [0, 2n - 2] and the maximum digit is (2n - 2) - (0) + 1 = 2n - 1
        diag1 = new boolean[(n << 1) - 1];
        diag2 = new boolean[(n << 1) - 1];
        dfs(0);
        return ans;
    }
}