站长网站优点成都私人网站建设

代码1：

class Solution {bool check[7];vector <int> path;vector<vector<int>> ret;public:vector<vector<int>> permute(vector<int>& nums) {for(int i=0;i<7;i++)
{check[i]=true;
}dfs(nums);
return ret;}void dfs(vector <int>& nums)
{if(path.size()==nums.size())
{ret.push_back(path);//回去再处理check和path;
return ;}int size=nums.size();for(int i=0;i<size;i++)
{
if(check[i]==true)
{path.push_back(nums[i]);check[i]=false;
dfs(nums);
path.pop_back();
check[i]=true;}}}};

这里使用全局变量去记录，不足在于要手动处理入口和出口的状态修改逻辑（这里可以对比着看下面的第二种，第二种只是用了ret这个全局口袋去接收）

这种写法的dfs只用传递一个固定不变的参数，只有全局变量在处理变化（如哪些数字已使用，记录完整的一组数据的收纳）

递归出口是path的size和nums的size相同，即path是完整的一种排列，此时入库（收入ret中）
此时，return 将会返回上级函数，此时path应该失去最后一个数，check对映的这个数应该改为true(true代表没被使用过，false代表使用过)

很明显，在出口处我们没有处理check和path，所以要在出来函数的另一端（即入口后）去写对check和path的逻辑

代码2：

class Solution {vector<vector<int>> ret;public:vector<vector<int>> permute(vector<int>& nums) {vector<int> path;
int total_size=nums.size();dfs(nums,path,total_size);return ret;}void dfs(vector<int> nums,vector<int> path,int total_size)
{
if(path.size()==total_size)
{
ret.push_back(path);
return;}int size=nums.size();for(int i=0;i<size;i++)
{//制造新的nums和path
vector<int> tmp=nums;
vector<int>ppath=path;
ppath.push_back(tmp[i]);
swap(tmp[size-1],tmp[i]);
tmp.pop_back();
dfs(tmp,ppath,total_size);}}};

代码2的效果是很差的，dfs的for里面制造新的nums和path，基本就是手动画树状图，把可选的nums和对应此时的path的情况都列出来，供代码运行，这么大的工作量之后的效果，就是形成在出入口像二叉树一样自然自动的感觉，其实就是单一改为多方向，二叉树实现传入参数可退回（即path在return会自动减去当前加上的），因为二叉树的传入参数变换是单一的，而全排列的传入参数会有多个方向所以就创建了ppath这个中转接口，以实现可逆效果

2、子集【力扣】

这个题目有两种思路：一是以是否选择i数据的决策树，这个决策树在叶子节点会得到我们需要的答案，二是以i个数据为划分（如对{1，2，3}来说数据量为1的答案有{1}，{2}，{3}这三个）

dfs传入参数k是为了统计是否到达叶子节点

class Solution {vector<vector<int>> ret;vector<int> path;
public:void dfs(vector<int> &nums,int k)
{
ret.push_back(path);
int size=nums.size();for(int i=k;i<size;i++)
{
path.push_back(nums[i]);
dfs(nums,i+1);
path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}
};