快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区

一、LeetCode 46.全排列

方法一：

•         递归+回溯
•         对于这种问题，我们首先要将过程给画出来，画出来的图叫做策略树
•         根据策略树，我们再将其转换为对应的代码

        决策树画出来后，代码也就知道大概的思路了

        1.发现这里每个路径到头的话就是一个结果

        2.所以定义两个全局变量 vector<vector<int>> ret代表结果 vector<int>path 代表路径

        3.当path路径的长度=长度时，然后终止递归return返回上一层，记录下这个结果到ret

        4.重点是每一层递归进入的同时，进入的时候path进入，然后如果返回上一层的时候要

           把path的上一层入进去的拿出来，换成其他的，因为有多种结果

        5.然后还有一个最细节的，需要一个bool 数组来记录这个位置是否使用过

        6.因为这里全排列可以随机排列，使用for循环递归其他的，通过bool数组来选择，如果

           用过就不能用了

代码：

时间复杂度：

                O(n * !n)

空间复杂度：

                O(n * !n)

二、LeetCode 78.子集

方法一：

•         递归+回溯
•         对于这种问题，我们首先要将过程给画出来，画出来的图叫做策略树
•         根据策略树，我们再将其转换为对应的代码

        1.每次选只能选择后面的，不能选择前面的，因为是子集，不是全排列那种题目

        2.每次递归都存入结果

        3.这里就不需要bool数组判断了，直接选择后面的就行

代码：

时间复杂度：

                O（n * 2^n）

空间复杂度：

                O（n）

三、LeetCode 17.电话号码的字母组合

方法一：

•         递归+回溯
•         对于这种问题，我们首先要将过程给画出来，画出来的图叫做策略树
•         根据策略树，我们再将其转换为对应的代码

        1.这里不做过多讲解，跟前面的两题类似

        2.直接看代码

代码：

时间复杂度：

                O（3^n * 4^m）

空间复杂度：

                O（n+m）

n 是三个字母的数字个数

m是四个字母的数字个数

总结：🌟

这三道题都是关于深度优先遍历   递归+回溯的

递归进入存入结果，回溯回到上次的结果，继续下次循环

对于递归的使用一定要熟悉，并且这类题目一定要画出策略树，根据策略树来写对应的代码

加油，为了更好的明天！