回溯算法总结

回溯算法

回溯算法简介

回溯算法就是dfs，也就是N叉树的遍历。

回溯法重要的就是单层递归的路径。模板为

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

回溯算法一般是为了解决暴力递归解决不了的问题。

可以使用回溯算法解决如下问题

组合问题比如说 216.组合总和III
切割问题比如说 93.复原IP地址 131.分割回文串
子集问题比如说 491.递增子序列第90题.子集II
排列问题比如说 47.全排列 II
棋盘问题比如说第51题. N皇后

步骤

第一步确认参数参数一般包括数组
- 有没有startIndex 看这个回溯算法的集合是不是与之前的有关，如果有就需要
  
  不需要startIndex 比如说全排列这种，上一层递归和这层递归集合之间就没有关系。比如[1, 2] 和 [2, 1]。只是去重有关，去重后面说
  
  需要startIndex 比如说子集或者划分，那种就是上一层递归与当前这层有关的，因为集合里面使用过的元素不应该再使用了，所以要使用startIndex
第二步确认递归终结条件
- 有一些回溯问题中，递归时不要进行return，因为找到一个可行解之后这颗子树后面还有可行解，比如说子集，[1, 2]找到之后可能还有[1, 2, 3]
第三步确认单层逻辑
- 一般是横向遍历加递归，这一步最重要的就是去重。去重分很多种，第一种是单层去重 ,“树层去重”。第二种是一个递归里面去重,“树枝去重”。
  - “树层去重”：单层去重是说一棵树同一层去重，一般是两种方式
```
for (int i = begin; i < candidates.length; i++) {
    // 这种情况需要先将nums排列好，并且used是成员变量，这种既可以“树层去重”也可以“树枝去重”
    if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == 0)
        continue;
    path.add(candidates[i]);
    used[i] = 1;
    backtracking(candidates, ...);
    used[i] = 0;
    path.removeLast();
}
```
    还有一种就是使用hashset局部变量或者取值范围不大的使用数组代替hashset，可以进行“树层去重”
```
HashSet<Integer> set = new HashSet<>();
for (int i = begin; i < nums.length; i++) {
    if (set.contains(nums[i]))
        continue;
    set.add(nums[i]);
    path.add(nums[i]);
    backtracking(nums, i + 1);
    path.removeLast();
}
```
  - “树枝去重”：一个递归里面去重，一般是 used[i] == 1
- 简枝，主要是三个地方
  - 方法终结条件那里可以提前结束这次递归，比如说现在这个条件已经不符合终止条件了，提前退出这层递归。在一个集合里面找几个数的和与目标值相同。
```
if (sum > k)
    return;
```
  - 一个是单层要遍历几个元素，比如说切分合理IP字段那个题，一个字段最多三个数，所以可以在这里做限制
  - 第二个就是符不符合条件，符合条件在进行回溯，不然就continue跳过去
```
for (int i = begin; i < begin + 3 && i < s.length(); i++) {
    if (isValidV2(s, begin, i)) {
        path.add(s.substring(begin, i + 1));
        backtrackingV2(s, i + 1);
        path.removeLast();
    }
}
```