回溯

回溯的本质是穷举，列出所有的组合，从中找到符合的答案。

回溯的模板

每次递归都是为了找到路径的其中一个组成节点，符合条件的路径就是其中一个答案。

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

for循环的开始下标是0还是startIndex

一般情况下都是0，主要考虑什么时候是startIndex：

  • 当数组有序，这一层选了某个数字之后，下一层不能选更小的数字，比如大部分组合问题
  • 字符串，这一层选了某个子串，下一层要从后一个索引位置开始，比如切割问题

去重

树层去重

一般用到used[]数组都是全局的，可用于数层或者树枝；

有时候也可以放backTracking内部，只用于本树层

1
2
3
4
5
6
7
8
// 使用全局used[]数组
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
    continue;
}
// 不用used[]数组，改用startIndex
if ( i > startIndex && candidates[i] == candidates[i - 1] ) {
    continue;
}

树枝去重

1
2
3
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == true) {
    continue;
}

剪枝

TODO