46. 全排列
78. 子集
77. 组合
39. 组合总和
22. 括号生成
回溯法是DFS递归遍历决策树的过程。
解题步骤：
- 画出递归的树状图，子节点是下一层的递归，理清思路。重点考虑两个维度，同一条链上的和同一层级(即结果集中的同一位置)的。第47题重复排列used的数组的两层含义表现这一点最明显
- 选择与撤销选择
- 最后再考虑如何剪枝，一般会用到其他数据结构。如47题用Set或boolean数组避免重复，60题第k个排列数的剪枝。
建议每一道题都画出递归的树状图来。
某种程度上说，动态规划的暴力求解阶段就是回溯算法。如果问题具有重叠子问题性质，就可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。因此在遇到一个题想使用回溯法的时候，要想一下，能不能改成动态规划的解法，例如：91. 解码方法，回溯法超时，应该用动态规划。
**排列问题，**讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，用 used 数组(inTheList数组)； **组合问题，**不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，用 start 变量。
排序一般是剪枝的前提，很多题需要先排序再剪枝。例如：47. 全排列(二)、 90. 子集(二)
Difficulty: 困难
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
思路：要遍历寻找过所有可能的路径并记录下来，为了不影响其他路径，要用回溯法。
先写回溯法的框架，再填充细节，比如valid方法和addToList方法，留在最后写。
遍历第一行，以第一行的每一个格子为起点，寻找可能的路径。如果棋子放到当前位置board[r][i]打破了N皇后规则，那就跳过当前位置。如果不打破，就继续往下一行放，直至放满了每一行，就找到了一种可行解。别忘了为了不影响下一种可能路径的遍历，要恢复现场。
public List<List<String>> solveNQueens(int n) {
List<List<String>> lists = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] chars : board) Arrays.fill(chars, '.');
backtrack(board, 0, lists);
return lists;
}
private void backtrack(char[][] board, int r, List<List<String>> lists) {
//r=length，说明找到了一条路径。
if (r == board.length) {
addToLists(board, lists);
return;
}
for (int i = 0; i < board.length; i++) {
//不打破N皇后才放棋子，否则直接下一个i。
if (valid(board, r, i)) {
//放置棋子到当前位置
board[r][i] = 'Q';
//递归遍历下一行
backtrack(board, r + 1, lists);
//恢复现场
board[r][i] = '.';
}
}
}
private boolean valid(char[][] board, int r, int c) {
for (int i = 0; i < r; i++) { //这一列
if (board[i][c] == 'Q') {
return false;
}
}
for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) { //左上角
if (board[i][j] == 'Q') {
return false;
}
}
for (int i = r - 1, j = c + 1; i >= 0 && j < board.length; i--, j++) { //右上角
if (board[i][j] == 'Q') {
return false;
}
}
//下面没有摆放棋子，因此不需要遍历左下角和右下角。
return true;
}
private void addToLists(char[][] board, List<List<String>> lists) {
List<String> list = new ArrayList<>();
for (char[] chars : board) {
StringBuilder sb = new StringBuilder();
for (char c : chars) {
sb.append(c);
}
list.add(sb.toString());
}
lists.add(list);
}可以优化的点：根据N皇后对角线规律，O(1)判断是不是这一条线上已经有其他棋子了。参考题解
Difficulty: 中等
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示：
board和word中只包含大写和小写英文字母。1 <= board.length <= 2001 <= board[i].length <= 2001 <= word.length <= 10^3
思路：基础的回溯法。DFS寻找是否存在，为了避免重复进行标记，这一层遍历结束以后恢复标记，避免影响别的路径。
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (word.charAt(0) == board[i][j] && backtrack(i, j, 0, word, visited, board)) {
return true;
}
}
}
return false;
}
private boolean backtrack(int i, int j, int idx, String word, boolean[][] visited, char[][] board) {
if (idx == word.length()) {
return true;
}
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word.charAt(idx) || visited[i][j]) {
return false;
}
visited[i][j] = true;
if (backtrack(i + 1, j, idx + 1, word, visited, board)
|| backtrack(i - 1, j, idx + 1, word, visited, board)
|| backtrack(i, j + 1, idx + 1, word, visited, board)
|| backtrack(i, j - 1, idx + 1, word, visited, board)) {
return true;
}
// 回溯
visited[i][j] = false;
return false;
}Difficulty: 中等
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路：经典回溯法。
如果当前元素在链路中，应该跳过当前元素。used[i]
递归使用过当前元素之后，要进行恢复，避免影响其他链路的递归。list.remove(list.size() - 1); used[i] = false;。
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
backtrack(lists, new ArrayList<Integer>(), new boolean[nums.length], nums);
return lists;
}
private void backtrack(List<List<Integer>> lists, List<Integer> list, boolean[] used, int[] nums){
if(list.size() == nums.length){
lists.add(new ArrayList(list));
return;
}
for(int i = 0; i < nums.length; i++){
if(!used[i]){
used[i] = true;
list.add(nums[i]);
backtrack(lists, list, used, nums);
list.remove(list.size() - 1);
used[i] = false;
}
}
}相关高频题：
Difficulty: 中等
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,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]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
思路：回溯法。
与46. 全排列相同的是，如果当前元素在链路中，应该跳过当前元素。used[i]
再考虑有重复元素：如果本层使用过与当前元素相等的数，也应该跳过当前元素。 怎么判断这种情况呢？如果当前值与前一个位置相等，并且前一个位置不在链路中，那么本层一定使用过前一个位置的值。不在当前链路中即!used[i - 1]。因此排除重复元素的判断条件为：if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
Arrays.sort(nums);
backtrack(lists, new ArrayList<>(), nums, new boolean[nums.length]);
return lists;
}
private void backtrack(List<List<Integer>> lists, List<Integer> list,
int[] nums, boolean[] inTheList) {
if (list.size() == nums.length) {
lists.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (inTheList[i] || (i > 0 && nums[i] == nums[i - 1] && !inTheList[i - 1])) {
continue;
}
inTheList[i] = true;
list.add(nums[i]);
backtrack(lists, list, nums, inTheList);
inTheList[i] = false;
list.remove(list.size() - 1);
}
}相关高频题：
Difficulty: 中等
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
思路：回溯法。每次进入递归函数都先加一次list，用start变量控制只能向数组后面遍历，避免重复。
时间复杂度：考虑到每个元素都得添加到list中的操作，时间复杂度是O(N^2)--每个元素都可以选择添加或者不添加。总共2^N种选择。
空间复杂度：(Cn1 + 2Cn2 + 3Cn3 + ... + nCnn)=n * 2^(n-1)
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
backtrack(lists, new ArrayList<>(), nums, 0);
return lists;
}
private void backtrack(List<List<Integer>> lists , List<Integer> list,
int [] nums, int start){
lists.add(new ArrayList<>(list));
for(int i = start; i < nums.length; i++){
list.add(nums[i]);
backtrack(lists, list, nums, i + 1);
list.remove(list.size() - 1);
}
}拓展其他思路：
位掩码方法：每个元素都可以选或者不选，用0和1二进制表示。 效率没有回溯高，因为回溯的参数idx是递增的，剪枝了。
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int n = 1 << nums.length; //2^len `1 <= nums.length <= 10`，不会越界。
for (int i = 0; i < n; i++) { //0-2^len-1
List<Integer> sub = new ArrayList<Integer>();
for (int j = 0; j < nums.length; j++) {
if (((i >> j) & 1) == 1) {
sub.add(nums[j]);
}
}
res.add(sub);
}
return res;
}相关高频题：
Difficulty: 中等
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路：与47. 全排列(二)对46. 全排列的改进相同。使用boolean数组，对于同一层，排除重复元素。
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> lists = new ArrayList<>();
boolean[] inTheList = new boolean[nums.length];
backtrack(nums, 0, lists, new ArrayList<Integer>(), inTheList);
return lists;
}
private void backtrack(int[] nums, int start, List<List<Integer>> lists,
List<Integer> list, boolean[] inTheList) {
lists.add(new ArrayList<Integer>(list));
for (int i = start; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !inTheList[i - 1]) {
continue;
}
list.add(nums[i]);
inTheList[i] = true;
backtrack(nums, i + 1, lists, list, inTheList);
list.remove(list.size() - 1);
inTheList[i] = false;
}
}改进：对于组合问题，排除同一层其实不需要boolean数组。boolean数组是为了解决排列问题的inTheList引入的，只用组合问题的start变量也可以排除同层的重复。
if (i > start && nums[i] == nums[i - 1])，说明相等值已经添加到了同层，需要跳过。
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
Arrays.sort(nums); //排序
backtrack(nums, 0, new ArrayList<>(), lists);
return lists;
}
private void backtrack(int[] nums, int start, ArrayList<Integer> list, List<List<Integer>> lists) {
lists.add(new ArrayList<>(list));
for (int i = start; i < nums.length; i++) {
//和上个数字相等就跳过
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
list.add(nums[i]);
backtrack(nums, i + 1, list, lists);
list.remove(list.size() - 1);
}
}Difficulty: 中等
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
思路：回溯法。用start变量控制只能向数组后面遍历，避免重复。
已经选择了[1,2]，到2开头时，没必要选[2,1]。因此只选后面的数就可以了。
应该根据n和k的大小关系进行剪枝，比如[1,2,3,4]，如果k=4，只需要1234dfs下去就可以了，后面就没必要继续遍历了。
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), 1, n, k);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> list, int start, int n, int k){
if(k == 0){
res.add(new ArrayList<>(list));
return;
}
for(int i = start; i <= n - k + 1; i++){
list.add(i);
backtrack(res, list, i + 1, n, k - 1);
list.remove(list.size() - 1);
}
}相关高频题：
Difficulty: 中等
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示：
1 <= candidates.length <= 301 <= candidates[i] <= 200candidate中的每个元素都是独一无二的。1 <= target <= 500
思路：与77. 组合相同，属于典型的组合问题。用start变量控制只能向数组后面遍历，避免重复。
考虑如何剪枝：先排序数组，排序一般是剪枝的前提。排序以后，如果当前位置已经比target大了，后面的一定也比target大，没必要再继续递归遍历。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> lists = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return lists;
}
Arrays.sort(candidates);
backtrack(lists, new ArrayList<Integer>(), 0, target, candidates);
return lists;
}
private void backtrack(List<List<Integer>> lists, List<Integer> list, int start, int target, int[] candidates) {
if (target < 0) {
return;
}
if (target == 0) {
lists.add(new ArrayList(list));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > target) {
break;
}
list.add(candidates[i]);
backtrack(lists, list, i, target - candidates[i], candidates);
list.remove(list.size() - 1);
}
}相关高频题：
377. 组合总和 Ⅳ 动态规划
Difficulty: 中等
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
思路：与90. 子集(二)对78. 子集的改进相同，为了避免相同位置有相同的值，当i > start && candidates[i] == candidates[i - 1]时，跳过。
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> lists = new ArrayList<>();
if (candidates.length == 0) {
return lists;
}
Arrays.sort(candidates);
List<Integer> list = new ArrayList<>();
dfs(candidates, candidates.length, 0, target, list, lists);
return lists;
}
private void dfs(int[] candidates, int len, int start, int target, List<Integer> list, List<List<Integer>> lists) {
if (target == 0) {
lists.add(new ArrayList<>(list));
return;
}
for (int i = start; i < len; i++) {
if (target < candidates[i]) {
break;
}
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
dfs(candidates, len, i + 1, target - candidates[i], list, lists);
list.remove(list.size() - 1);
}
}Difficulty: 中等
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
思路：不能包含重复，因此用start，从小到大开始选取。
这道题主要复杂在剪枝的细节考虑全，其他和40. 组合总和(二)差不多。
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> lists = new ArrayList<>();
// 一开始做一些特殊判断
if (k <= 0 || n <= 0 || k >= n) {
return lists;
}
// 寻找 n 的上限：[9, 8, ... , (9 - k + 1)]，它们的和为 (19 - k) * k / 2
// 比上限还大，就不用搜索了：
if (n > (19 - k) * k / 2) {
return lists;
}
List<Integer> list = new ArrayList<>();
backtrack(k, n, 1, list, lists);
return lists;
}
private void backtrack(int k, int target, int start, List<Integer> list, List<List<Integer>> lists) {
// 剪枝：[start, 9] 这个区间里的数都不够 k 个，不用继续往下搜索
if (10 - start < k) {
return;
}
if (k == 0 && target == 0) {
lists.add(new ArrayList<>(list));
return;
}
for (int i = start; i <= 10 - k; i++) {
// 剪枝
if (target < i) {
break;
}
list.add(i);
backtrack(k - 1, target - i, i + 1, list, lists);
list.remove(list.size() - 1);
}
}字节实习加面的四面遇到过
Difficulty: 中等
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
思路：非常典型的回溯法。用string数组存key和value的对应关系，画图出图来就比较简单了。
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return list;
}
backtrack(list, new StringBuilder(), digits);
return list;
}
public void backtrack(List<String> list, StringBuilder sb, String digits) {
if (sb.length() == digits.length()) {
list.add(sb.toString());
return;
}
int idx = digits.charAt(sb.length()) - '0';
for (char c : KEYS[idx].toCharArray()) {
sb.append(c);
backtrack(list, sb, digits);
sb.deleteCharAt(sb.length() - 1);
}
}Difficulty: 中等
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
思路：回溯法。这里采用的用掉一个左括号，左括号数量-1。左括号只要够，就可以继续添加。当右括号数量大于左括号的时候，可以添加右括号。
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
dfs(list, new StringBuilder(), n, n);
return list;
}
private void dfs(List<String> list, StringBuilder sb, int left, int right) {
if (left == 0 && right == 0) {
list.add(sb.toString());
return;
}
if (left > 0) {
sb.append("(");
dfs(list, sb, left - 1, right);
sb.deleteCharAt(sb.length() - 1);
}
if (right > 0 && left < right) {
sb.append(")");
dfs(list, sb, left, right - 1);
sb.deleteCharAt(sb.length() - 1);
}
}Difficulty: 中等
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000s仅由数字组成
思路：回溯法。如果用StringBuilder，需要回退，用String不需要回退。传入的就是一个新的String。
注意剪枝，先写基础条件，再想办法剪枝。如果后面剩的数太多了，比如还有最后一组，但还有5位数，那就没必要继续下去了
public List<String> restoreIpAddresses(String s) {
List<String> list = new ArrayList<>();
backtrack(list, 0, 0, s, "");
return list;
}
private void backtrack(List<String> list, int start, int depth, String s,String pre){
if (depth > 0 && depth < 4) {
pre += ".";
}
if (start == s.length() && depth == 4) {
list.add(pre);
}
for (int i = start; i < start + 3 && i < s.length(); i++) {
//以0开头只能是0
if (i != start && s.charAt(start) == '0') {
break;
}
//如果剩余的数太多了，还剩一个数了，但有4位，不可能达到。
if (s.length() - start > 3 * (4 - depth)) {
break;
}
if (Integer.valueOf(s.substring(start, i + 1)) <= 255) {
backtrack(list, i + 1, depth + 1, s, pre + s.substring(start, i + 1));
}
}
}Difficulty: 简单
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
思路1：根左右，先序遍历沿路添加即可。
思路2：其实这是一道典型的回溯法的题
//1. 先序遍历
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
dfs(root, list, new StringBuilder());
return list;
}
private void dfs(TreeNode root, List<String> list, StringBuilder path) {
if (root == null) {
return;
}
path.append(root.val);
if (root.left == null && root.right == null) {
list.add(path.toString());
}
dfs(root.left, list, new StringBuilder(path).append("->"));
dfs(root.right, list, new StringBuilder(path).append("->"));
}
//2. 回溯法 共用一个StringBuilder，每层递归之后，在返回上一层之前，删除这一层添加的
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
backtrack(root, list, new StringBuilder());
return list;
}
private void backtrack(TreeNode root, List<String> list, StringBuilder sb) {
if (root == null) {
return;
}
int preLength = sb.length();
sb.append(root.val);
if (root.left == null && root.right == null) {
list.add(sb.toString());
} else {
sb.append("->");
backtrack(root.left, list, sb);
backtrack(root.right, list, sb);
}
sb.setLength(preLength); //回溯 删掉这一层加的
}Difficulty: 中等
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
思路：与257. 二叉树的所有路径相同，回溯法。
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> lists=new ArrayList<>();
dfs(root,sum, lists, new ArrayList<Integer>());
return lists;
}
private void dfs(TreeNode root, int sum, List<List<Integer>> res, ArrayList<Integer> tmp) {
if (root == null) return;
tmp.add(root.val);
if (root.left == null && root.right == null && sum - root.val == 0) res.add(new ArrayList<>(tmp));
dfs(root.left, sum - root.val, res, tmp);
dfs(root.right, sum - root.val, res, tmp);
tmp.remove(tmp.size() - 1);
}⚡Difficulty: 中等
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
思路一：双递归 O(N^2)
思路二：回溯 用一个list保持到当前的所有可能的路径和。 平均情况下树的深度为logN，平均时间复杂度为O(NlogN)，最差情况O(N^2)
思路三：回溯+hashmap O(N) 比较难想到。key为从root到当前的路径和，value为这种路径和的个数。以当前节点结束的路径和=root到当前路径和的个数 - root到沿路结点的路径和等于target的个数。
//方法一：双递归 给每一个结点做DFS O(N^2)
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return ret;
}
private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ret = 0;
if (root.val == sum) {
ret++;
}
ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
return ret;
}
//方法二：list回溯
class Solution {
int cnt = 0;
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return cnt;
}
ArrayList<Integer> list = new ArrayList<>();
// if(root!=null) list.add(root.val);
backtrack(list, root, sum);
return cnt;
}
private void backtrack(ArrayList<Integer> list, TreeNode root, int sum) {
if (root == null) {
return;
}
for (int i = 0; i < list.size(); i++) {
list.set(i, list.get(i) + root.val);
if (list.get(i) == sum) {
cnt++;
}
}
list.add(root.val);
if (root.val == sum) {
cnt++;
}
backtrack(list, root.left, sum);
backtrack(list, root.right, sum);
//为了不影响其他路径 回溯 删除当前节点的，并把list中每个值都减回去。
list.remove(list.size() - 1);
for (int i = 0; i < list.size(); i++) {
list.set(i, list.get(i) - root.val);
}
}
}
//方法三：HashMap回溯
public int pathSum(TreeNode root, int sum) {
HashMap<Integer, Integer> preSum = new HashMap();
preSum.put(0, 1);
return helper(root, 0, sum, preSum);
}
public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
if (root == null) {
return 0;
}
currSum += root.val;
int res = preSum.getOrDefault(currSum - target, 0);
preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);
res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
//为了不影响其他路径，回溯
preSum.put(currSum, preSum.get(currSum) - 1);
return res;
}Difficulty: 困难
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 109。
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
**思路：画出树状结构。统计以某个数为前缀的符合条件的数的个数，如果个数小于k，直接剪掉这一部分。**虽然没用回溯法，但和回溯画图剪枝很像，因此放到这一部分。
public int findKthNumber(int n, int k) {
int curr = 1;
k = k - 1; //先把1去掉
while (k > 0) {
int steps = calSteps(n, curr);
if (steps <= k) {
//同层下一个 比如1开头的跳过，从2开头的开始查找 或10开头的跳过，从11开头的查找
curr += 1;
k -= steps;
} else {
curr *= 10; //进入下一层 比如1开头的，进入10开头的
k -= 1;
}
}
return curr;
}
//特别注意！use long in case of overflow
public int calSteps(int n, long n1) {
int steps = 0;
long n2 = n1 + 1;
while (n1 <= n) {
steps += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return steps;
}lc491. Increasing Subsequences(Medium) LeetCode/力扣
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。
数组中的整数范围是[-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
思路：递增序列，不能先排序，然后根据nums[i]和nums[i-1]的关系判断。
往下一层相当于数组idx+1，每层都使用一个Set标记这一层已经用过的数字： 不会出现两个[4,7]，但又不影响[4,7,7].
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> lists=new ArrayList<>();
backtrack(lists,nums,0,new ArrayList<Integer>());
return lists;
}
private void backtrack(List<List<Integer>> lists, int[] nums, int start, List<Integer> list){
if(list.size()>1) lists.add(new ArrayList<Integer>(list));
HashSet<Integer> set=new HashSet<>(); //set的作用：同一层相同元素只加进去一次
for(int i=start;i<nums.length;i++){
if(!set.contains(nums[i])){
if(list.size()==0||nums[i]>=list.get(list.size()-1)){
list.add(nums[i]);
set.add(nums[i]);
backtrack(lists,nums,i+1,list);
list.remove(list.size()-1);
}
}
}
}因为输入的范围是限定的[-100,100]，所以每一层可以用indexed的boolean数组代替Set进行标记
lc784. Letter Case Permutation (Easy) LeetCode/力扣
思路：如果是字符，就可以派生出一个新分支
大小写互换：大写字母-32，小写字母+32 可以直接和32做异或运算
chars[idx]=(char) (chars[idx] ^ (1 << 5)) 不要忘记强制类型转换回(char)
public List<String> letterCasePermutation(String S) {
int len = S.length();
List<String> list = new ArrayList<>();
if (len == 0) {
return list;
}
dfs(0, S.toCharArray(), list);
return list;
}
private void dfs(int idx, char[] chars, List<String> list) {
if (idx == chars.length) {
list.add(new String(chars));
return;
}
dfs(idx+1,chars,list);
// 如果是字符，就可以派生出一个新分支
if (Character.isLetter(chars[idx])) {
// 大小写互换：必须有(char)强制类型转换
chars[idx]=(char) (chars[idx] ^ (1 << 5));
dfs(idx + 1, chars, list);
}
}lc113. Path Sum II (Medium) LeetCode/力扣/剑指offer
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明:叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
思路：树的回溯和其他回溯法是一样的。 注意左右不是null的判断
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> lists=new ArrayList<>();
if(root==null) return lists;
backtrack(root,sum,lists,new ArrayList<Integer>());
return lists;
}
private void backtrack(TreeNode node, int sum, List<List<Integer>> lists,
List<Integer> list){
list.add(node.val);
if(node.left==null&&node.right==null&&node.val==sum){
lists.add(new ArrayList(list));
}else{
if(node.left!=null){
backtrack(node.left,sum-node.val,lists,list);
}
if(node.right!=null){
backtrack(node.right,sum-node.val,lists,list);
}
}
list.remove(list.size()-1); //遍历结束这个结点的子树，删除
}lc842. 将数组拆分成斐波那契序列
Split Array into Fibonacci Sequence (Medium) LeetCode/
力扣
给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上，斐波那契式序列是一个非负整数列表 F，且满足：
0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
F.length >= 3；
对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 S 拆分出来的所有斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入："123456579"
输出：[123,456,579]
示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]
示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。
示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示：
1 <= S.length <= 200
字符串 S 中只含有数字。
答案方法：穷举，确定所有可能的第一项和第二项。 我第一时间写的也是这种，很多细节的地方可能出错。for循环判断条件可以用函数 用startsWith()函数判断 或者我用的indexOf()!=0
class Solution {
public List<Integer> splitIntoFibonacci(String S) {
int N = S.length();
for (int i = 0; i < Math.min(10, N); ++i) {
if (S.charAt(0) == '0' && i > 0) break;
long a = Long.valueOf(S.substring(0, i+1));
if (a >= Integer.MAX_VALUE) break;
search: for (int j = i+1; j < Math.min(i+10, N); ++j) {
if (S.charAt(i+1) == '0' && j > i+1) break;
long b = Long.valueOf(S.substring(i+1, j+1));
if (b >= Integer.MAX_VALUE) break;
List<Integer> fib = new ArrayList<>();
fib.add((int) a);
fib.add((int) b);
int k = j + 1;
while (k < N) {
long nxt = fib.get(fib.size() - 2) + fib.get(fib.size() - 1);
String nxtS = String.valueOf(nxt);
if (nxt <= Integer.MAX_VALUE && S.substring(k).startsWith(nxtS)) {
k += nxtS.length();
fib.add((int) nxt);
}
else continue search;
}
if (fib.size() >= 3) return fib;
}
}
return new ArrayList<Integer>();
}
}回溯法：这种回溯法还是挺难想的，需要分好多情况讨论 +Ⅲ
确定了前两项以后，只有在发现等于时候，才会进入递归。其余都在同一层里很快就循环结束了。
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> ans = new ArrayList<>();
helper(S, ans, 0);
return ans;
}
public boolean helper(String s, List<Integer> ans, int idx) {
if (idx == s.length() && ans.size() >= 3) {
return true;
}
for (int i=idx; i<s.length(); i++) {
if (s.charAt(idx) == '0' && i > idx) {
break;
}
long num = Long.parseLong(s.substring(idx, i+1));
if (num > Integer.MAX_VALUE) {
break;
}
int size = ans.size();
// early termination
if (size >= 2 && num > ans.get(size-1)+ans.get(size-2)) {
break;
}
if (size <= 1 || num == ans.get(size-1)+ans.get(size-2)) {
ans.add((int)num);
// branch pruning. if one branch has found fib seq, return true to upper call
if (helper(s, ans, i+1)) {
return true;
}
ans.remove(ans.size()-1);
}
}
return false;
}
链接：https://leetcode.com/problems/split-array-into-fibonacci-sequence/discuss/133936/short-and-fast-backtracking-solution累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字'0'-'9'的字符串，编写一个算法来判断给定输入是否是累加数。
说明:累加序列里的数不会以 0 开头，所以不会出现1, 2, 03 或者1, 02, 3的情况。
示例 1:
输入: "112358"
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例2:
输入: "199100199"
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
思路：仿照上面那一题的回溯法写的。题目没说必须是int，要用long
确定了前两项以后，只有在发现等于时候，才会进入递归。其余都在同一层里很快就循环结束了。
public boolean isAdditiveNumber(String num) {
long f1=0; long f2=0;
return backtrack(num, 0, f1, f2,0);
}
private boolean backtrack(String s, int start, long f1, long f2, int numbercnt){
if(start==s.length()&&numbercnt>2) return true;
//注意要写(i-start)<=s.length()/2限制长度：
for(int i=start;i<s.length()&&(i-start)<=s.length()/2;i++){
if(s.charAt(start)=='0'&&i>start) break;
long thisnum=Long.parseLong(s.substring(start,i+1));
//if(thisnum>Integer.MAX_VALUE) break; //numbercnt是0或1也可以break，因为i是递增的，已经检测过之前的结果
if(numbercnt>=2&&thisnum>f1+f2) break;
if(numbercnt==0){
if(backtrack(s,i+1,thisnum,f2,1)) return true;
}
if(numbercnt==1){
if(backtrack(s,i+1,f1,thisnum,2)) return true;
}
//错误：必须指明numbercnt>=2 输入"111" f1=1 f2=0（第一层的f2取默认值0） thisnum=1 得到错误的true结果。
if(numbercnt>1&&thisnum==f1+f2){
if(backtrack(s,i+1,f2,thisnum,numbercnt+1)) return true; //错误：numbercnt++
}
}
return false;
}这个答案也挺好的：用的BigInteger和long，递归和迭代两种方法。用函数作为判断条件： https://leetcode.com/problems/additive-number/discuss/75567/Java-Recursive-and-Iterative-Solutions
for (int i = 1; i <= n / 2; ++i)
for (int j = 1; Math.max(j, i) <= n - i - j; ++j)
if (isValid(i, j, num)) return true;
return false;