算法：回溯问题（未完待续~~）

回溯算法简介

DFS 和回溯算法区别

DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

何时使用回溯算法

当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

怎么样写回溯算法

(从上而下，※代表难点，根据题目而变化)
①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
②根据题意，确立结束条件
③找准选择列表(与函数参数相关),与第一步紧密关联※
④判断是否需要剪枝
⑤作出选择，递归调用，进入下一层
⑥撤销选择

回溯问题的类型

这里先给出，我总结的回溯问题类型，并给出相应的 leetcode题目(一直更新)，然后再说如何去编写。特别关注搜索类型的，搜索类的搞懂，你就真的搞懂回溯算法了,，是前面两类是基础，帮助你培养思维

类型	题目链接
子集、组合	子集、子集 II、组合、组合总和、组合总和 II
全排列	全排列、全排列 II、字符串的全排列、字母大小写全排列
搜索	解数独、单词搜索、N皇后、分割回文串、二进制手表

注意：子集、组合与排列是不同性质的概念。子集、组合是无关顺序的，而排列是和元素顺序有关的，如 [1，2] 和 [2，1] 是同一个组合(子集)，但 [1,2] 和 [2,1] 是两种不一样的排列！！！！因此被分为两类问题

例题

子集、组合类型问题

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

解题步骤如下

1、画递归树

递归树

观察上图可得，选择列表里的数，都是选择路径(红色框)后面的数，比如[1]这条路径，他后面的选择列表只有 “2、3”，[2] 这条路径后面只有 “3” 这个选择，那么这个时候，就应该使用一个参数 start，来标识当前的选择列表的起始位置。也就是标识每一层的状态，因此被形象的称为 “状态变量“，最终函数声明如下

public void backtrace(int[] nums,List<Integer> path, int start);
// path用于记录结果集，要把最后的path加入结果集
// start 用于记录每一层的状态

2、找结束条件

此题非常特殊，所有路径都应该加入结果集，所以不存在结束条件。或者说当 start 参数越过数组边界的时候，程序就自己跳过下一层递归了，因此不需要手写结束条件,直接加入结果集。

3、找选择列表

在1中已经提到过了，子集问题的选择列表，是上一条选择路径之后的数,即

for(int i=start;i<nums.size();i++)

4、做出选择(即for 循环里面的)

public void backtrace(int[] nums,List<Integer> path, int start,List res)
{
    for(int i=start;i<nums.length;i++)
    {
        // 加入结果集
        path.add(nums[i]);
        // 对于 java 来说 需要把路径 “复制一遍”再添加
        res.add(new ArrayList<>(path));
        backtrace(nums,path,i+1,res);

    }
}

5、撤销选择

整体的 backtrack 函数如下

public void backtrace(int[] nums,List<Integer> path, int start,List res)
{
    for(int i=start;i<nums.length;i++)
    {
        // 加入结果集
        path.add(nums[i]);
        res.add(new ArrayList<>(path));
        backtrace(nums,path,i+1,res);
        
        // 撤销选择
        path.remove(path.size()-1);
    }
}