算法练习：回溯
俗称：穷举、暴力破解
思路
解决一个回溯问题，实际上就是一个决策树的遍历过程。
以全排列为例：
站在当前节点上做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝，因为 2 这个树枝在你身后，已经选择过来。
关键要素：
- 路径：已经做出的选择。
- 选择列表：当前可以做的选择。
- 结束条件：到达决策树底层，无法再做选择的条件。
伪代码框架：
result = []
def backtrack(路径, 选择列表):
if 结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
路径和选择列表：可以直接保存，也可以通过某种方式推算出来
- 在节点的前序遍历位置，做选择
- 在节点的后序遍历位置，撤销选择
结束条件就是遍历到树的底层叶子节点，这里也就是选择列表为空的时候
练习
class Solution {
private List<List<Integer>> result;
private LinkedList<Integer> choose;
private boolean[] used;
public List<List<Integer>> permute(int[] nums) {
result = new LinkedList<>();
choose = new LinkedList<>();
used = new boolean[nums.length];
backtrack(nums, choose, used);
return result;
}
//路径：nums和used组合，获取待路径的列表
//选择列表：choose
private void backtrack(int[] nums, LinkedList<Integer> choose, boolean[] used) {
//结束条件
if (choose.size() == nums.length) {
result.add(new LinkedList(choose));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
//做选择
choose.add(nums[i]);
used[i] = true;
//递归
backtrack(nums, choose, used);
//撤销选择
used[i] = false;
choose.removeLast();
}
}
}
参考
- https://labuladong.github.io/algo/4/29/105/