1.全排列
46. 全排列 - 力扣（LeetCode）https://leetcode.cn/problems/permutations/description/这道题是一道穷举的题，最终把所有全排列弄出来返回就行。用for循环也能穷举出来，但数据量大就会使效率很慢，所以用递归来帮我们把所有情况枚举出来。首先画出决策树(越详细越好)：如1 2 3，有三个空格。开始后要么选1，要么选2，要么选3。选1就是1_ _，选2就是2_ _，选3就是3_ _。在第一种选法基础上进行第二次选，第二个位置依旧可选1选2选3，但数不能重复，所以1这个枝减掉，然后选2选3变成了12_ 13_，其余同理：
最后一次也一样把重复的剪了，最后可得到结果：
画好决策树后可以发现，每个结点都是枚举出整个数组里的所有数，只不过有些枝被干了，当每个结点干同样事时就可把决策树改为递归了。2.设计代码，要有全局变量，需要有个二维数组ret记录最终结果，还有个int类的数组path记录路径上的选择。深搜刚开始path什么也没有，选1后给path添1，到下一层……当path长度等于nums长度时说明发现了一种情况，然后把结果放ret中：
(回到上一层进入了分枝时要把2干了)那怎么剪枝呢？如当选1进入下一层时如何避免选到1呢？所以需要一个bool类型的check数组，帮我们判断这个数在路径中是否已被使用(记录下标)。因此比如开始选2时，就把bool类型的check[1]设为true，下次选数时先去check中看一下。2.dfs函数：我们仅需关心某个节点在干嘛，就是把数组中所有数枚举一遍，只要这些数没被用过，就把它添加到path后面。下面一些细节问题：1.回溯：向上回去时要把最后的元素干了，也要把check标记复原回上层的样子。2.剪枝：check可帮我们剪枝。3.递归出口：遇到叶子结点，直接添加结果。下面来实现(题目最大为6，所以给7 nums)：
2.子集
78. 子集 - 力扣（LeetCode）https://leetcode.cn/problems/subsets/description/解法一：1.先想一个决策树。2.根据决策树来设计代码(想一下全局变量、dfs函数体设计、细节问题)。决策树这里先想想如何能不重不漏的把所有子集枚举出来，如nums[1,2,3]，子集是这个数组里选或不选某一些数形成的一个新集合就是子集，所以我们可以单独盯着某一个数看选还是不选。开始后可以不选1，可以选1，若不选1相当于得到了一个空集，选1相当于得到了1。接下来在选完的基础上对2进行操作，可以不选2，可以选2。不选2在空集基础上又什么也没选还是空集，在空集基础上选2此时相当于得到了2。在选1的基础上也可以不选或选2，不选2得到了1，选2得到了1,2……：
这样在决策树叶子结点中最终得到的都是子集。下面仅需把决策树转化为代码，既然要在叶子结点收集信息，仅需记录一下路径中我们选择的东西，所以要有个全局的path，int[] path；还需要有一个int[][]ret来记录结果。dfs设计盯着某一个位置看干什么事情，任意一个位置再考虑下一次那个数选还是不选，所以dfs不仅要有数组，还要知道当前要选哪个位置 dfs[nums,i]，dfs干的是在数组中I位置的数选还是不选。若选了path+=nums[i]再到下一层，不选择则直接dfs(nums,i+1)到下一层dfs。下面再考虑一些细节问题：这里不存在剪枝，弄全局的path回溯时记得恢复现场，当在某一层添加完元素进入到了下一层，当在这一层向上返回时要把添加的干了。出口：到叶子节点这一层就可以向上返回了，也就是i==nums.size时，此时把path放ret里。
解法二：1.画决策树。2.设计代码(关注全局、dfs)。如nums[1,2,3]，此时换一种思考方式：当子集里只有0个，1个，2个，3个元素时。刚开始是空集，当子集里只有一个元素时可选1选2选3，此时得到子集1，子集2，子集3。当子集里有2个元素时，就是在之前基础上多添加一个元素，1的基础上可多添2，3；2的基础上可多添3；3的基础上什么也不能选……当子集有三个元素时可在1，2基础上选3：
每次选数时都是从已选数的后面开始选，我们进入递归时此时的路径就是一个结果(决策树每个结点都是我们想要的结果)。下面来设计：全局变量int[]path，int[][]ret。dfs：每个结点是从当前位置开始，向后开始依次枚举，所以dfs(nums，pos)，从pos开始枚举。这里没有剪枝，没有出口，进入函数就添加结果。
下面来实现：
