回溯思想

通关进度

题目 说明
组合 通关
输出二叉树的所有路径 通关
路径总和 通关

参考资料

透彻理解什么是回溯

暴力递归

回溯模板

1
2
3
4
5
6
7
8
9
10
11
void dfs(param) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择本层集合元素) {
        处理节点;
        dfs();
        撤销处理;
    }
}

回溯解决的问题

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

回溯模板

回溯类似 N 叉树 遍历

1
2
3
4
5
6
7
8
9
10
11
void order(TNode root) {
    if (root == null) { // 递归终止条件
        return;
    }
    // 处理节点
    handler node;
    // 遍历 N 个子树
    for (int i = 0; i < node.length(); i++) {
        order(i);
    }
}

确定递归终止条件 

1
2
3
4
if (终止条件) {
    存储答案;
    return;
}

回溯搜索过程

集合的大小构成树的宽度，递归的深度构成树的深度 

1
2
3
4
5
6
7
// for循环就是遍历集合区间，理解成 N 叉树的分支结构
// for 循环可以理解是横向遍历，dfs（递归）就是纵向遍历
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    dfs(路径，选择列表); // 递归
    回溯，撤销处理结果
}
1
2
3
4
5
6
7
8
9
10
11
12
void dfs(参数) {
   if (终止条件) {
       存放结果;
       return;
   }

   for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
       处理节点;
       dfs(路径，选择列表); // 递归
       回溯，撤销处理结果
   }
}

组合

77. 组合

总结

组合问题：记住一句话，不管不同集合之间的组合，还是同一集合中的组合中。N叉树模型中，for循环往往是控制递归树的横向遍历，递归层数（终止条件）往往取决于树的高度，剩下的结合题意进行剪枝操作。
如果是单个集合来求组合的话，就需要startIndex,
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex

问题

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

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

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],
]

N 叉树模型

  1. 绘制出递归树
  2. 对于同一集合的组合问题，N 叉树模型需要确定 startIndex
  3. 确定递归参数和终止条件
  4. 确定单层遍历逻辑，一般 for 负责横向遍历，递归是纵向遍历
  5. 剪枝操作

题目分析

  • 无重复元素
  • 同一集合之间的组合

算法思路

给出一种递归树形结构，可以发现集合宽度n转换成递归树的宽度，组合数元素个数k转换成递归层数，因此每次到了第k层，就找到了答案。

确定递归函数参数和返回值：

1
2
3
4
List<List<Integer>> result; // 根据测试用例定义存储最终答案的集合
List<Integer> path; // 定义存储每条遍历分支的答案集合

public void dfs(int n, int k, int startIndex)

dfs 参数 startIndex 用来记录本层递归中，集合遍历的起点，每次从集合中选择元素，可供选择的范围会变化的。譬如，在集合[1,2,3,4]中选取了 1，进入下一层递归，startIndex也更随变化。

确定递归函数终止条件 ：

上述分析可知，当递归层数到了第k层，说明找到了该条路径中的答案，由于每遍历路径的每一层会向path数组加入答案，因此path数组长度达到k，便到达递归终止条件。 

1
2
3
4
if (path.size == k) {
	 result.add(new ArrayList<>(path));
	 return;
}

由于Java ArrayList特性这里不能直接将path传入给result，他是动态变化的，需要传入一份值的拷贝

确定单层遍历过程 

1
2
3
4
5
for (int i = startIndex; i <= n; i++) { // 横向遍历树
	path.add(i); // 将该分支的答案加入path
	dfs(n, k, i + 1); // 进入递归树的下一层继续枚举
	path.remove(path.size() - 1); // 回溯到上次层递归，即上一层树
}

原始版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List<List<Integer>> result; // 根据测试用例定义存储最终答案的集合
List<Integer> path; // 定义存储每条遍历分支的答案集合

public List<List<Integer>> combine(int n, int k) {
    result = new ArrayList<>();
    path = new ArrayList<>();
    dfs(n, k, 1);
    return result;
}

public void dfs(int n, int k, int startIndex) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
    }
    for (int i = startIndex; i <= n; i++) {
        path.add(i);
        dfs(n, k, i + 1);
        path.remove(path.size()-1);
    }
}

剪枝优化

上述未优化版本有着大量无意义的枚举，时间复杂度偏高，这里考虑剪枝优化，将不满足条件的直接过滤掉

可以剪枝的地方就在递归中每一层的 for 循环所选择的起始位置。在本题中，如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索。

  • 已经选择的答案个数：path.size();
  • 还需要的答案个数为: k - path.size();
  • 因此遍历集合最多从 n-(k-path.size()) + 1 开始 [ + 1 是因为包括起始位置，需要是一个左闭的集合]
1
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 剪枝优化
List<List<Integer>> result; // 根据测试用例定义存储最终答案的集合
List<Integer> path; // 定义存储每条遍历分支的答案集合

public List<List<Integer>> combine(int n, int k) {
    result = new ArrayList<>();
    path = new ArrayList<>();
    dfs(n, k, 1);
    return result;
}

public void dfs(int n, int k, int startIndex) {
    // 递归终止条件
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 单层遍历过程
    for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        dfs(n, k, i + 1);
        path.remove(path.size() - 1);
    }
}

二叉树模型

  1. 绘制出递归树，一般属于从左向右的尝试模型
  2. 确定递归函数参数含义，如index表示当前遍历的位置
  3. 确定递归终止条件，如index==arr.length表示从左到右走完即退出
  4. 确定index位置（每次位置）的状态，一般有选择和不选择两种状态
  5. 剪枝操作

从左到右尝试的二叉递归模型

找到一个长度为n的序列a的所有子序列

  • 确定递归函数参数dfs(int index, int n)，参数n表示当前位置是index，原始序列长度为n

  • 使用变量temp存放被选中的序列

  • 进入dfs(index,n)前[1, index-1]的位置是选择过的，而[index, n]位置是没有做出选择的

  • 递归函数dfs(index, n)意义是在index位置上做出选择，然后继续求解子问题dfs(index + 1, n)

递归函数的选择

  • 对于index位置，有两条路径
    • 选择a[index]上的序列，因此把a[index]放入记录答案的数组temp中，然后执行下一层枚举，执行结束后需要对temp回溯，返回递归树上层。
    • 不选择a[index]上的序列，直接执行dfs(index + 1, n)
  • 在整个递归调用的过程中，index是从小到大递增的，当index增加到 n+1（说明遍历完毕，需要退出） 的时候，记录答案并终止递归

优化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<Integer> temp = new ArrayList<>();
void dfs(int index, int n) {
	if (index == n + 1) {
		记录答案
		 ...
		return;
	}
	// 选择当前位置
	temp.add(index);
	dfs(index + 1, n, k);
	temp.remove(temp.size() - 1);
	
	// 不考虑当前位置
	dfs(index + 1, n, k);
}

回到本题

  • 在 n 个元素选 k 个，在 dfs 的时候需要多传入一个参数 k，即 dfs(index,n,k)。
  • 在每次进入这个 dfs 函数时，我们都去判断当前 temp 的长度是否为 k
  • 如果为 k，就把 temp 加入答案并直接返回

原始版本：

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
List<List<Integer>> ans;
List<Integer> temp;

public void dfs(int index, int n, int k) {
	// 答案数组满足长度k返回答案
	if (temp.size() == k) {
		ans.add(new ArrayList<>(temp));
		return;
	}
	// 递归终止条件
	if (index == n + 1) {
		return;
	}
	// 考虑当前位置的选择
	temp.add(index);
	dfs(index + 1, n, k);
	temp.remove(temp.size() - 1);

	// 不考虑当前位置的选择
	dfs(index + 1, n, k);
}

public List<List<Integer>> combine(int n, int k) {
	ans = new ArrayList<>();
	temp = new ArrayList<>();
	dfs(1, n, k);
	return ans;
}

剪枝操作

  • 如果当前temp的大小为 $s$， 未做出选择的区间[index,n]的长度为 $t$
  • 如果 $s+t<k$
  • 即使 $t$ 个都被选中，也不可能构造出一个长度为 $k$ 的序列
1
2
3
if (temp.size() + (n - cur + 1) < k) {
    return;
}

优化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void dfs(int index, int n, int k) {
	// 剪枝操作
	if (temp.size() + (n - index + 1) < k) {
    	return;
	}
	// 答案数组满足长度k返回答案
	if (temp.size() == k) {
		ans.add(new ArrayList<>(temp));
		return;
	}
	// 递归终止条件
	if (index == n + 1) {
		return;
	}
	// 考虑当前位置的选择
	temp.add(index);
	dfs(index + 1, n, k);
	temp.remove(temp.size() - 1);

	// 不考虑当前位置的选择
	dfs(index + 1, n, k);
}

继续优化

  • cur = n + 1 时，一定不可能出现 temp.size>k， 因为自始至终 temp.size 绝不可能大于 k，它等于 k 的时候就会被第二处 if 记录答案并返回
  • cur = n + 1 时，temp.size=k，会被第二个 if 记录答案并返回
  • cur = n + 1 时，temp.size<k，一定会在 cur<n+1 某个位置发现 temp.size+t<k，会被第一个 if 剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void dfs(int index, int n, int k) {
	// 剪枝：temp 长度加上区间 [index, n] 的长度小于 k，不可能构造出长度为 k 的 temp
 	if (temp.size() + (n - index + 1) < k) {
		return;
	}
    // 记录合法的答案
	if (temp.size() == k) {
    	ans.add(new ArrayList<Integer>(temp));
    	return;
	}
	// 考虑选择当前位置
	temp.add(index);
	dfs(index + 1, n, k);
	temp.remove(temp.size() - 1);
	
	// 考虑不选择当前位置
	dfs(index + 1, n, k);
}

输出二叉树的所有路径

257. 二叉树的所有路径

问题

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

回溯思路

遍历得到 A-B-D 后通过回溯得到 A-B-E：

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
List<String> ans = new ArrayList<>();

public List<String> binaryTreePaths(TreeNode root) {
    dfs(root, new ArrayList<>());
    return ans;
}

public void dfs(TreeNode root, List<Integer> list) {
    // 递归终止条件
    if (root == null) {
        return;
    }
    list.add(root.val);
    // 记录结果
    if (root.left == null && root.right == null) {
        ans.add(getPathString(list));
    }
    dfs(root.left, list);
    dfs(root.right, list);
    list.remove(list.size() - 1);
}

public String getPathString(List<Integer> list) {
    StringBuilder sb = new StringBuilder();
    sb.append(list.get(0));
    for (int i = 1; i < list.size(); i++) {
        sb.append("->").append(list.get(i));
    }
    return sb.toString();
}

二叉树遍历思路

输出二叉树的所有路径

思考

传统二叉树遍历与回溯解决的区别

路径总和

113. 路径总和 II

问题

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

回溯思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<Integer> path = new LinkedList<>();
    dfs(root, targetSum, path);
    return res;
}

public void dfs(TreeNode root, int targetSum, List<Integer> path) {
    // 递归终止条件
    if (root == null) {
        return;
    }

    targetSum -= root.val;
    path.add(root.val);
    if (targetSum == 0 && root.left == null && root.right == null) {
        res.add(new LinkedList<>(path));
    }
    dfs(root.left, targetSum, path);
    dfs(root.right, targetSum, path);
    path.remove(path.size() - 1);
}

二叉树遍历思路

路径总和

路径总和Ⅱ

回溯专题

组合总和

39. 组合总和

问题

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

N 叉树模型

  1. 绘制出递归树
  2. 对于同一集合的组合问题，N叉树模型需要确定startIndex
  3. 确定递归参数和终止条件
  4. 确定单层遍历逻辑，一般for负责横向遍历，递归是纵向遍历
  5. 剪枝操作
  6. 由于元素无限制重复选取，进入下一层递归 i不需要 +1 操作，关键是看递归树写代码

题目分析

  • 数组无重复元素
  • 同一集合之间的组合
  • 元素无限制重复选取

由于集合元素可以无限制被重复选取，仅仅是有 target 的限制，又考虑到 N 叉树模型中 for 循环控制横向遍历，取决于集合元素个数，一条分支路径中代表一种答案，因此只可能在每条路径的遍历中出现重复枚举，而每一棵子树的横向遍历是不可能重复的，从而递归层数是无限制的，因此递归终止条件理解为该条分支路径中答案总和超过target 就必须返回

确定递归函数参数 ：

  • 存储最终答案的数组ans
  • 存储单个路径的答案数组path
  • 本题还需要startIndex来控制for循环的起始位置
  • 记录当前分支上的总和curSum
1
2
3
4
List<List<Integer>> ans;
List<Integer> path;

public void dfs(int[] candidates, int target, int startIndex, int curSum)

确定递归终止条件：

1
2
3
4
5
6
7
8
// 不合法，直接返回
if (curSum > target) {
	return;
}
if (sum == target) {
	ans.add(new ArrayList<>(path));
	return;
}

确定单层遍历逻辑：

1
2
3
4
5
6
7
8
9
10
11
for (int i = startIndex; i < candidates.length; ++i) { // 控制每棵子树的横向遍历
	// 将当前节点的值放入path，同时更新单个路径上的sum
	curSum += candidates[i];
	path.add(cadidates[i]);
	// 遍历当前分支的下一层
	// 由于每条路径上的答案可以重复，因此不需要i+1
	dfs(cadidates, target, i, curSum);
	// 返回递归树的上一层
	sum -= candidates[i];
	path.remove(path.size() - 1);
}

原始版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void dfs(int[] candidates, int target, int startIndex, int curSum) {
    if (curSum > target) {
        return;
    }
    if (curSum == target) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = startIndex; i < candidates.length; ++i) { // 控制每棵子树的横向遍历
        // 将当前节点的值放入path，同时更新单个路径上的sum
        curSum += candidates[i];
        path.add(candidates[i]);
        // 遍历当前分支的下一层
        // 由于每条路径上的答案可以重复，因此不需要i+1
        dfs(candidates, target, i, curSum);
        // 返回递归树的上一层
        curSum -= candidates[i];
        path.remove(path.size() - 1);
    }
}

剪枝操作：

对于 curSum 已经大于 target 的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断 curSum > target 的话就返回。
其实如果已经知道下一层的 curSum 会大于 target，就没有必要进入下一层递归了。
对总集合排序之后，如果下一层的 sum（就是本层的 sum + candidates[i]，因为进入下一层递归时sum+=candiates[i]）已经大于target，就可以结束本轮for循环的遍历。

1
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

优化版本：

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
List<List<Integer>> ans;
List<Integer> path;

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    ans = new ArrayList<>();
    path = new ArrayList<>();
    // 对集合排序，便于剪枝
    Arrays.sort(candidates);
    dfs(candidates, target, 0, 0);
    return ans;
}

public void dfs(int[] candidates, int target, int startIndex, int curSum) {
    // 递归终止条件
    if (curSum == target) {
        ans.add(new ArrayList<>(path));
        return;
    }

    // 单层遍历逻辑
    for (int i = startIndex; i < candidates.length && curSum + candidates[i] <= target; ++i) { // for控制横向遍历
        // 将当前节点的值放入path，同时更新单个路径上的sum
        curSum += candidates[i];
        path.add(candidates[i]);
        // 遍历当前分支的下一层
        // 由于每条路径上的答案可以重复，因此不需要i+1
        dfs(candidates, target, i, curSum);
        // 返回递归树的上一层
        curSum -= candidates[i];
        path.remove(path.size() - 1);
    }
}

二叉树模型

  1. 绘制出递归树，一般属于从左向右的尝试模型
  2. 确定递归函数参数含义，如index表示当前遍历的位置
  3. 确定递归终止条件，如index==arr.length表示从左到右走完即退出
  4. 确定index位置（每次位置）的状态，一般有选择和不选择两种状态
  5. 剪枝操作

从左到右尝试的二叉递归模型

确定递归函数参数 ：

定义递归函数 dfs(target,combine,idx) 表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine

确定递归终止条件 ：

递归的终止条件为 target ≤ 0 或者 candidates 数组被全部用完

确定单层递归逻辑 ：

  • 当前的函数中，每次我们可以选择跳过不用第 idx 个数，即执行 dfs(target,combine,idx+1)
  • 可以选择使用第 idx 个数，即执行 dfs(target−candidates[idx],combine,idx)。注意到每个数字可以被无限制重复选取，因此搜索的下标仍为idx 

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
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> combine = new ArrayList<>();
    dfs(candidates, target, ans, combine, 0);
    return ans;
}

public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int index) {

    if (index == candidates.length) {
        return;
    }

    if (target == 0) {
        ans.add(new ArrayList<>(combine));
        return;
    }
    // 不选择当前位置 //搜索树横向
    dfs(candidates, target, ans, combine, index + 1);
    // 选择当前位置
    if (target - candidates[index] >= 0) {
        combine.add(candidates[index]);
        dfs(candidates, target - candidates[index], ans, combine, index);
        combine.remove(combine.size() - 1);
    }
}

分割回文串

131. 分割回文串

问题

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

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

题目分析

  • 切割问题

  • 判断回文

    [组合问题] — 选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…
    [切割问题] — 切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…

确定递归函数参数：

  • path保存每一条分支的结果
  • ans保存最终答案
  • 与组合问题一样，切割过的地方不能重复切割，需要起点startIndex
1
2
3
4
List<String> path;
List<List<String>> ans;

public void dfs(String s, int startIndex)

确定递归函数终止条件 ：

从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。

在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。 

1
2
3
4
if (startIndex >= s.length()) {
	ans.add(new ArrayList<>(path));
	return;
}

确定单层搜索逻辑：

在 for (int i = startIndex; i < s.size(); i++) 循环中，我们定义了起始位置 startIndex，那么 [startIndex,i] 就是要截取的子串

首先判断这个子串是不是回文，如果是回文，就加入在path中，path用来记录切割过的回文子串 

1
2
3
4
5
6
7
8
9
10
11
for (int i = startIndex; i < s.length(); i++) {
    if (isPalindrome(s, startIndex, i)) { // 是回文子串
        // 获取[startIndex,i]在s中的子串
       String str = s.substring(startIndex, i + 1);
       path.add(str);
    } else {                // 如果不是则直接跳过
        continue;
    }
    dfs(s, i + 1); // 寻找i+1为起始位置的子串
    path.remove(path.size() - 1);        // 回溯过程，弹出本次已经填在的子串
}

注意切割过的位置，不能重复切割，所以，dfs(s, i + 1)传入下一层的起始位置为 i + 1

判断回文：

1
2
3
4
5
6
7
8
public boolean isPalindrome(String s, int startIndex, int end) {
    for (int i = startIndex, j = end; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
    }
    return 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
List<String> path;
List<List<String>> ans;
public List<List<String>> partition(String s) {
    path = new ArrayList<>();
    ans = new ArrayList<>();
    dfs(s, 0);
    return ans;
}

public void dfs(String s, int startIndex) {
    if (startIndex >= s.length()) {
        ans.add(new ArrayList<>(path));
        return;
    }

    for (int i = startIndex; i < s.length(); i++) {
        if (isPalindrome(s, startIndex, i)) { // 是回文子串
            // 获取[startIndex,i]在s中的子串
            String str = s.substring(startIndex, i + 1);
            path.add(str);
        } else {                // 如果不是则直接跳过
            continue;
        }
        dfs(s, i + 1); // 寻找i+1为起始位置的子串
        path.remove(path.size() - 1);        // 回溯过程，弹出本次已经填在的子串
    }

}

public boolean isPalindrome(String s, int startIndex, int end) {
    for (int i = startIndex, j = end; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
    }
    return true;
}

子集问题

78. 子集

问题

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

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

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

N 叉树模型

题目分析

  • 把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点
  • 取过的元素不会重复取，写回溯算法的时候，for 就要从startIndex 开始，而不是从 0 开始

确定递归函数参数 ：

1
2
3
List<List<Integer>> ans;
List<Integer> path;
public void dfs(int[] nums, int startIndex)

确定递归终止条件 ：

剩余集合为空时，就是叶子节点。 就是 startIndex 已经大于数组的长度了，就终止了，因为没有元素可取 

1
2
3
if (startIndex >= nums.length)) {
    return;
}

其实可以不需要加终止条件，因为 startIndex >= nums.length，本层 for 循环本来也结束了。

确定单层遍历逻辑 ：

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树

1
2
3
4
5
for (int i = startIndex; i < nums.length; i++) {
    path.add(nums[i]);    // 子集收集元素
    dfs(nums, i + 1);  // 注意从i+1开始，元素不重复取
    path.remove(path.size() - 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
List<List<Integer>> ans;
List<Integer> path;
public List<List<Integer>> subsets(int[] nums) {
    ans = new ArrayList<>();
    path = new ArrayList<>();

    dfs(nums, 0);
    return ans;
}

public void dfs(int[] nums, int startIndex) {
    // 收集子集，要放在终止添加的上面，否则会漏掉自己
    ans.add(new ArrayList<>(path));

    if (startIndex >= nums.length){
        return;
    }

    for (int i = startIndex; i < nums.length; i++){
        path.add(nums[i]);
        dfs(nums, i + 1);
        path.remove(path.size() - 1);
    }
}

二叉树版本

确定递归函数参数：

  • dfs(cur,n) 参数表示当前位置是 cur，原序列总长度为n
  • 原序列的每个位置在答案序列中的状态有被选中和不被选中

  • 用 t 数组存放已经被选出的数字

    确定递归终止条件：

在整个递归调用的过程中，cur 是从小到大递增的，当 cur 增加到 n 的时候，记录答案并终止递归

确定单次遍历逻辑：

  • 在进入dfs(cur,n)之前 [0,cur−1] 位置的状态是确定的，而 [cur,n−1] 内位置的状态是不确定的

  • dfs(cur,n) 需要确定 cur 位置的状态，然后求解子问题 dfs(cur+1,n)

  • 对于 cur 位置，我们需要考虑 a[cur] 取或者不取

    • 如果取，我们需要把 a[cur] 放入一个临时的答案数组中（即上面代码中的 t），再执行 dfs(cur+1,n)，执行结束后需要对 t 进行回溯
    • 如果不取，则直接执行 dfs(cur+1,n) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();

public List<List<Integer>> subsets(int[] nums) {
    dfs(0, nums);
    return ans;
}

public void dfs(int cur, int[] nums) {
    // 当 cur 增加到 n 的时候，记录答案并终止递归。
    if (cur == nums.length) {
        ans.add(new ArrayList<Integer>(t));
        return;
    }
    //选择当前位置
    t.add(nums[cur]);
    dfs(cur + 1, nums);
    t.remove(t.size() - 1);
     //不选择当前位置
    dfs(cur + 1, nums);
}

排列问题

46. 全排列

问题

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

N 叉树模型

确定递归函数参数 ：

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了 

1
2
3
List<List<Integer>> ans;
List<Integer> path;
public void dfs(int[] nums, boolean[] used)

确定递归终止条件：

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点 

1
2
3
4
if (path.size() == nums.length) {
    ans.add(new ArrayList<>(path));
    return;
}

确定单层搜索逻辑：

和[组合问题、切割问题和子集问题]最大的不同就是for循环里不用startIndex

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。

used数组，其实就是记录此时path里都有哪些元素使用，一个排列里一个元素只能使用一次。

1
2
3
4
5
6
7
8
for (int i = 0; i < nums.length; i++) {
    if (used[i] == true) continue; // path里已经收录的元素，直接跳过
    used[i] = true;
    path.add(nums[i]);
    dfs(nums, used);
    path.remove(path.size() - 1);
    used[i] = false;
}

参考答案

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
List<List<Integer>> ans;
List<Integer> path;
boolean [] used;
public List<List<Integer>> permute(int[] nums) {

    if (nums.length == 0){
        return ans;
    }
    used = new boolean[nums.length];
    ans = new ArrayList<>();
    path = new ArrayList<>();
    dfs(nums, used);
    return ans;
}

public void dfs(int[] nums, boolean[] used) {
    if (path.size() == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i] == true) continue; // path里已经收录的元素，直接跳过
        used[i] = true;
        path.add(nums[i]);
        dfs(nums, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

字母大小写全排列

784. 字母大小写全排列

问题

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

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

回溯

从左往右依次遍历字符，当在进行搜索时，搜索到字符串 $s$ 的第 $i$ 个字符 $c$ 时:

  • 如果 $c$ 为一个数字，则我们继续检测下一个字符；
  • 如果 $c$ 为一个字母，我们将字符中的第 $i$ 个字符 $c$ 改变大小写形式后，往后继续搜索，完成改写形式的子状态搜索后，我们将 $c$ 进行恢复，继续往后搜索；
  • 如果当前完成字符串搜索后，则表示当前的子状态已经搜索完成，该序列为全排列中的一个；

由于每个字符的大小写形式刚好差了 32，因此在大小写装换时可以用 $c\oplus 32$ 来进行转换和恢复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<String> letterCasePermutation(String s) {
    List<String> ans = new ArrayList<String>();
    dfs(s.toCharArray(), 0, ans);
    return ans;
}

public void dfs(char[] arr, int pos, List<String> res) {
    while (pos < arr.length && Character.isDigit(arr[pos])) {
        pos++;
    }
    if (pos == arr.length) {
        res.add(new String(arr));
        return;
    }
    arr[pos] ^= 32;
    dfs(arr, pos + 1, res);
    arr[pos] ^= 32;
    dfs(arr, pos + 1, res);
}

单词搜素

79. 单词搜索

问题

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

算法思想

从上到下、左到右遍历网格，每个坐标调用回溯方法，$i、j$ 表示网格坐标，$k$ 表示 word 的第 $k$ 个字符

确定递归终止条件：

  • 行或列索引越界，返回 false
  • 当前矩阵元素与目标字符不同，返回 false
  • 当前矩阵元素已经访问过，返回 false
  • 如果字符串 word 全部匹配，即 k=len(word)-1，返回 true

递推公式：

  1. 标记当前矩阵元素：将 broad[i][j] 修改为空字符 ''，代表此元素已经访问过，防止之后搜索时重复访问
  2. 搜索下一单元格：朝当前元素的上、下、左、右四个方向开启下层递归，只需要找到一个可行路径直接返回，并记录结果至 res
  3. 还原当前矩阵元素：将 broad[i][j] 元素还原至 初始值，即 work[k]
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
public boolean exist(char[][] board, String word) {

    char[] words = word.toCharArray();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, words, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
    if (i >= board.length || i < 0 ||
        j >= board[0].length || j < 0||
        board[i][j] != word[k]) {
        return false;
    }
    if (k == word.length - 1) {
        return true;
    }
    board[i][j] = '\0';
    boolean res = dfs(board, word, i + 1, j, k + 1) || // 右
                  dfs(board, word, i - 1, j, k + 1) || // 左
                  dfs(board, word, i, j + 1, k + 1) || // 下
                  dfs(board, word, i, j - 1, k + 1); // 上
    board[i][j] = word[k];
    return res;
}

复原 IP 地址

93. 复原 IP 地址

问题

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 

1
2
3
4
5
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

切割问题

确定递归函数参数：

  • path 存放分支的答案
  • ans 存放最终答案
  • startIndex 因为不能重复分割，记录下一层递归分割的起始位置。
  • pointNum 记录添加逗点的数量
1
2
3
4
StringBuilder path;
List<String> ans;

public void dfs(int startIndex, int pointNum)

确定递归终止条件 ：

本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。 pointNum表示逗点数量，pointNum为3说明字符串分成了4段了，然后验证一下第四段是否合法，如果合法就加入到结果集里 

1
2
3
4
5
6
7
if (pointNum == 3) { // 逗点数量为3时，分隔结束
	 // 判断第四段子字符串是否合法，如果合法就放进ans中
	if (isValid(s, startIndex, s.size() - 1)) {
        ans.add(s);
    }
    return;
}

确定单层搜索逻辑：

在 for (int i = startIndex; i < s.size(); i++) 循环中 [startIndex,i] 这个区间就是截取的子串，需要判断这个子串是否合法。

  • 如果合法就在字符串后面加上符号 . 表示已经分割
  • 如果不合法就结束本层循环，如下剪掉的分支

回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum 也要 -1

1
2
3
4
5
6
7
8
9
10
11
for (int i = startIndex; i < s.length(); i++) {
	 if (isValid(s, startIndex, i)) {
	 	  s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后⾯插⼊⼀个逗点
          pointNum++;
          dfs(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
          pointNum--;// 回溯
          s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点    
	} else {
		 break;
	}
}

判断子串是否合法 ：

  • 段位以 0 为开头的数字不合法
  • 段位里有非正整数字符不合法
  • 段位如果大于 255 了不合法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
public Boolean isValid(String s, int start, int end) {
	if (start > end) {
		return false;
	}
	if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
		return false;
	}
	int num = 0;
	for (int i = start; i <= end; i++) {
		if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
			return false;
		}
		num = num * 10 + (s.charAt(i) - '0');
		if (num > 255) { // 如果⼤于255了不合法
			return false;
		}
	}
	return 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
List<String> ans = new ArrayList<String>();
StringBuilder path = new StringBuilder();

public List<String> restoreIpAddresses(String s) {
    dfs(s, 0, 0);
    return ans;
}

// number表示stringbuilder中ip段的数量
public void dfs(String s, int start, int number) {
    // 如果start等于s的长度并且ip段的数量是4，则加入结果集，并返回
    if (start == s.length() && number == 4) {
        ans.add(path.toString());
        return;
    }
    // 如果start等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是start小于s的长度，则直接返回
    if (start == s.length() || number == 4) {
        return;
    }
    // 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
    for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0
            && Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) {
        // 如果ip段的长度大于1，并且第一位为0的话，continue
        if (i + 1 - start > 1 && s.charAt(start) - '0' == 0) {
            continue;
        }
        path.append(s.substring(start, i + 1));
        // 当stringBuilder里的网段数量小于3时，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点
        if (number < 3) {
            path.append(".");
        }
        number++;
        dfs(s, i + 1, number);
        number--;
        // 删除当前stringBuilder最后一个网段，注意考虑点的数量的问题
        path.delete(start + number, i + number + 2);
    }
}

电话号码的字母组合

17. 电话号码的字母组合

问题

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

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

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

题目分析

不同集合之间的组合

N 叉树模型

  1. 绘制出递归树
  2. 对于不同集合间的组合问题，N叉树模型不需要确定startIndex，遍历到集合中每一个元素，依次取元素中对应的映射即可
  3. 确定递归参数和终止条件
  4. 确定单层遍历逻辑，一般for负责横向遍历，递归是纵向遍历
  5. 剪枝操作

本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而组合和组合总和III 都是是求同一个集合中的组合！

  • 本题是数字映射到字母，是关于字母的组合问题
    • 尝试建立数字到字母的哈希映射
  • 如果题目对输入数据没有限制的情况下还需要单独考虑违规情况 1、#，但本题无需考虑

确定递归函数参数：

  • 定义path存储单个路径上的答案，ans存储最终答案
  • 题目中的字符串参数digits
  • 记录当前遍历digits里的数字的位置index
  • 数字到字母的映射数组letterMap
1
2
3
4
List<String> ans;
StringBuilder path;

public void dfs(String digits, int index, String)

确定递归终止条件 ：

终止条件就是如果 index 等于 输入的数字个数（digits.size） 

1
2
3
4
if (index == digits.size()) {
	ans.add(path);
	return;
}

确定单层遍历逻辑：

取index位置指向的数字，映射到对应字符串，用for循环处理字符集 

1
2
3
4
5
6
7
// str 表示当前index对应的字符串
String str = letterMap[digits.chart(index) - '0'];
for (int i = 0; i < str.length(); i++) {
	path.append(str.charAt(i));
	dfs(digits, letterMap, index + 1);
	path.deletCharAt(path.length() - 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
// 存储最终答案
List<String> ans;
// 存储单个路径的答案
StringBuilder path;

public List<String> letterCombinations(String digits) {
    ans = new ArrayList<>();
    path = new StringBuilder();

    if (digits == null || digits.length() == 0) {
        return ans;
    }
    // 构建数字到字符的映射
    String[] letterMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    dfs(digits, letterMap, 0);
    return ans;
}

public void dfs(String digits, String[] letterMap, int index) {
    // 递归终止条件
    if (index == digits.length()) {
        ans.add(path.toString());
        return;
    }
    // digits字符串中的单个数字对应的字符串
    String str = letterMap[digits.charAt(index) - '0'];
    // 单层遍历逻辑
    for (int i = 0; i < str.length(); ++i) { //控制横向遍历
        // 递归是控制单个分支
        // 当前答案加入path
        path.append(str.charAt(i));
        // 遍历递归树的下一层
        dfs(digits, letterMap, index + 1);
        // 递归结束后，path答案取出，恢复到刚进入dfs的状态
        path.deleteCharAt(path.length() - 1);
    }
}

括号生成问题

22. 括号生成

问题

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

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

题目分析

  • 左括号要求：只要剩余左括号数量大于 0，就可以添加 (
  • 右括号要求：序列中左括号数量必须大于右括号的数量才可以添加 (，并且 ) 的剩余数量大于 0

记 ( 为 left，) 为right，回溯如下，n = 2

  • 当前可使用的左右括号数量大于 0 时，可以产生继续递归，否则终止
  • 产生左分支时，只看当前是否还有左括号使用
  • 产生右分支时，除要求有右括号外，还要求剩余右括号数量一定大于左括号数量
  • 在左括号和右括号数量都剩余 0 时结束
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
public List<String> generateParenthesis(int n) {

    List<String> ans = new ArrayList<>();

    dfs(ans, new StringBuilder(), 0, 0, n);
    return ans;
}

/**
 * @param ans 当前递归得到的结果
 * @param cur 当前的括号串
 * @param open 左括号已经使用的个数
 * @param close 右括号已经使用的个数
 * @param max 序列长度最大值
 */
public void dfs(List<String> ans, StringBuilder cur, int open, int close, int max) {
    if (cur.length() == max * 2) {
        ans.add(cur.toString());
        return;
    }
    if (open < max) {
        cur.append('(');
        dfs(ans, cur, open + 1, close, max);
        cur.deleteCharAt(cur.length() - 1);
    }
    if (close < open) {
        cur.append(')');
        dfs(ans, cur, open, close + 1, max);
        cur.deleteCharAt(cur.length() - 1);
    }

}