概述

回溯的本质是穷举, 穷举所有可能, 然后选出答案
一般时间复杂度为指数级别, n在30以内
一般有几类问题, 组合, 子集, 排列, 图(N皇后)
回溯问题一般可以抽象成树, 写之前可以画图分析
和DP问题也可以通过题目区分, 一般要求枚举结果的是回溯, 问有多少种结果的是DP问题

模板

public List<List<int>> result = new List<List<int>>();
public List<List<int>> xxx()
    调用DFS(new List<int>());
    return result;

// 参数根据题目需要设置
private void DFS()
    if(终止条件)
        // 这里一定要new一个新数组
        subset.Add(new List<int> (subset));
        return;

    for(本层集合的元素)
        处理subset.Add()
        DFS();
        回溯subset.RemoveAt(subset.Count - 1);

组合

// N个数里面按一定规则找出k个数的集合
// 1. 如果一个集合求组合, 需要使用startIndex(for循环的起始位置), 如果每个元素回溯过程中只使用一次, 回溯的时候要使用i + 1, 否则多次使用, 每次都要从i开始
// 2. 如果从多个集合取组合, 每个集合之间相互不影响, 就可以不使用startIndex, 每次完整遍历本层的元素
// 3. 如果有重复的元素, 不可以重复使用, 一般先排序, 然后定义一个全局变量bool[] used
//    判断条件一般为 if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
//    回溯过程中记得修改used状态
LeetCode 77. 组合(一个集合, 元素使用一次, 无重复元素)
LeetCode 39. 组合总和(一个集合, 元素使用多次, 无重复元素)
LeetCode 40. 组合总和 II (一个集合, 元素使用一次, 重复元素)
LeetCode 216. 组合总和 III (一个集合, 元素使用一次, 无重复元素)
LeetCode 17. 电话号码的字母组合(多个集合, 元素使用一次, 无重复元素)

子集

// 一个N个数的集合里有多少符合条件的子集, 本质上是组合问题的一种扩展
// 与组合问题的一些区别
// 1. subset加入结果的位置是在进入DFS函数时
// 2. 子集问题相当于遍历树的所有节点，一般不考虑剪枝的情况
LeetCode 78. 子集(无重复元素)
LeetCode 90. 子集 II (有重复元素)
LeetCode 491. 递增子序列 (有重复元素, 且不能排序)

排列

// N个数按一定规则全排列，有几种排列方式
// 排列是对组合的另一种拓展, 选取全部元素
// 注意排列和子集的区别, {2, 1} {1, 2}是两种排列但是是一种子集
// 1. 不需要使用start Index, 每次for循环都是从0开始, 比如第一次取2, 第二次仍有可能取到1
// 2. 需要使用used还标记该元素是否已经使用过
LeetCode 46. 全排列(无重复元素)  AcWing 842. 排列数字
LeetCode 47. 全排列 II(有重复元素)