子集，组合

解题思路：

1.DFS 和回溯算法区别

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

2. 何时使用回溯算法

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

3. 怎么样写回溯算法 (从上而下，※代表难点，根据题目而变化)

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

4. 回溯问题的类型

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

leetcode题

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

5. 回到子集、组合类型问题上来 (ABC 三道例题)

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

解题步骤如下