Backtracking Template

2023-09-02

回溯算法

回溯算法通常用于搜索解空间。这样的解空间往往是组合爆炸式增长的，比如排列问题就是一个典型示例。

给定一个数字 ，打印出区间  中所有数字的排列。

对于 ，期望输出：

1
2
3
4
5
6
1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2

在这种情况下，我们需要使用回溯来解决问题。回溯会在每次做出决策、选择一个候选项扩展时保存一个“检查点”。

下面给出回溯算法的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
public void backtracking(List<Candidate> candidates, List<Candidate> partialSolution) {
    if (candidates.isEmpty()) {
        // 保存 / 检查 / 验证 当前部分解
    } else {
        for (Candidate cand : candidates) {
            // 从候选列表中移除 cand
            // 将 cand 加入当前部分解
            backtracking(candidates, partialSolution);
            // 从当前部分解中移除 cand
            // 将 cand 加回候选列表
        }
    }
}

下面对排列问题做一个部分“手动演练”：
1. 从 candidates 中选出 1，并移除它
2. 从剩余中选出 2，并移除它
3. 再选出 3，并移除它
4. 此时 candidates 为空，跳出，记录排列 [1,2,3]
5. 把 3 加回 candidates，但此时已无其他候选
6. 把 2 加回 candidates，移动到下一个候选 3
7. 从 candidates 中选出 3，并移除它
8. 再选出 2，并移除它
9. candidates 为空，跳出，记录排列 [1,3,2]
10. 依此类推…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
List<List<Integer>> permutations = new LinkedList<>();

public void backtrack(int n, boolean[] visited, List<Integer> solution) {
    if (solution.size() == n) {
        permutations.add(new LinkedList<>(solution));
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            solution.add(i);
            visited[i] = true;
            backtrack(n, visited, solution);
            visited[i] = false;
            solution.remove(solution.size() - 1);
        }
    }
}

显然，这里的时间复杂度并不是线性的，实际上与叶子节点数量一致，为 。