LeetCode78、46dfs深搜求解子集、全排列问题LeetCode 90、47 子集2 全排列2

LeetCode 78

问题描述： 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

回溯法中的子集树问题，相当于一个完全n叉树，此题中相当于完全二叉树，共有2⁽ⁿ⁺¹⁾-1个结点，2ⁿ个叶结点，从根节点到叶节点的分支连起来即对应所有的子集。其中假设左子树为1，选中；右子树为0，不选中。

void dfs(int dep,vector<int>& nums) { if(dep==n){ int size=track.size(); if(size==0) cout<<"null"<<endl;//空集输出null else for(int i=0;i<size;i++) cout<<track[i]<<" "; cout<<endl; return ; } track.push_back(nums[dep]);//只有两条分支，先选中，再不选中， dfs(dep+1,nums); //当分支过多时也可以用for循环代替 track.pop_back(); dfs(dep+1,nums); } int main() { int t; cin>>n; vector<int> nums;//只是想试一下传参，可以直接定义成全局变量数组 for(int i=0;i<n;i++){ cin>>t; nums.push_back(t); } dfs(0,nums); return 0; }

上面的写法是标准的二叉树，每个层都对应的一个数的选中与不选中，在做了洛谷P2404 自然数的拆分和P1157组合的输出之后，有了新的理解，每层的可以不按照一个数是否选中不选中来做，而是采取它们使用的前驱起始的做法，实现输出的字典序排列：这样写出来第一层可以认为是起始null，第二层是n叉树，后面随着结点的大小叉树在变。 该树的特征：子结点的下标一定要大于父结点的下标；树的高度不一定了；每次判定达到数组最后一个下标结束；每个结点对应一个子集(包括null结点)。

树的结构见下图！

#include <bits/stdc++.h> using namespace std; int n,nums[100]; vector<int> track; void dfs(int pre) { if(pre==0) cout<<"null"<<endl; else{ for(int i=0;i<track.size();i++) printf("=",track[i]); cout<<endl; }//每过一层的一个结点就要输出一次。 for(int i=pre;i<n;i++){//这也是递归结束的条件 track.push_back(nums[i]); dfs(i+1); track.pop_back(); } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>nums[i]; sort(nums,nums+n);//为了实现字典序输出，先排好序 dfs(0); return 0; }

LeetCode 46

问题描述： 给定一个没有重复数字的数组nums，返回其所有可能的全排列。

回溯法中的排列树问题，假设数组长度为n，则有 n! 个叶节点，对应 n! 个解

#include <bits/stdc++.h> using namespace std; int len; vector<int> track; int nums[1000],vis[1000];//全局变量，默认初始化为0 void dfs(int dep) { if(dep==len){ for(int i=0;i<len;i++) cout<<track[i]<<" "; cout<<endl; return ; } for(int i=0;i<len;i++){ if(vis[i]==0){ track.push_back(nums[i]); vis[i]=1; dfs(dep+1); track.pop_back(); vis[i]=0; } } } int main() { cin>>len; for(int i=0;i<len;i++) cin>>nums[i];//数组nums可能无序，最好排个序输出好看 dfs(0); return 0; }

最好再main函数里面加一个sort函数对nums数组进行从小到大的排序，这样通过上面方法的搜索可以实现按照字典序的输出。 再来看回溯法用正常递归的一种解法，这种不满足字典序输出：

class Solution { int len; vector<vector<int> >ans; public: vector<vector<int>> permute(vector<int>& nums) { len=nums.size(); Perm(0,nums); return ans; } void Perm(int dep,vector<int>& nums){ if(dep==len){ans.push_back(nums); return ;} for(int i=dep;i<len;i++){ swap(nums[i],nums[dep]); Perm(dep+1,nums); swap(nums[i],nums[dep]); } } };

以nums[]={1,2,3}为例，实现Perm(1,2,3)的递归可展开为： Perm{1,2,3}=1 Perm{2,3}+2 Perm{1,3}+3 Perm{1,2}……依次递推下去

LeetCode 90 子集2

问题描述： 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 Input

[1,2,2]

Output

[2], [1], [1,2,2], [2,2], [1,2], []

当不是该层的第一个结点时，如果其他结点出现重复，那么后一个结点的分支必然包括在前面重复的一个结点的分支之中。 因此只需要在上面子集1的思路上再多加一个条件判断即可：if(nums[i] != nums[i-1]) 如果是第一个结点，它前面没有结点，可直接加入不用判断if条件

#include <bits/stdc++.h> using namespace std; int n,nums[100]; vector<int> track; void dfs(int pre) { if(pre==0) cout<<"null"<<endl; else{ for(int i=0;i<track.size();i++) printf("=",track[i]); cout<<endl; } for(int i=pre;i<n;i++)//这也是递归结束条件 if(i==pre||nums[i]!=nums[i-1]){//如果i==pre为1后面就不判断了，直接条件成立，对应第一个先进入的情况 track.push_back(nums[i]); //如果i!=pre，即为0，再判断nums[i]与nums[i-1]进行剪枝 dfs(i+1); track.pop_back(); } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>nums[i]; sort(nums,nums+n);//先排序好实现字典序输出 dfs(0); return 0; }

LeetCode 47 全排列2

问题描述： 给定一个可包含重复数字的序列，返回所有不重复的全排列。 Input

[1,1,2]

Output

[1,1,2], [1,2,1], [2,1,1]

黑色的是正常写法的全排列树形表示，由于vis数组的出现我们可以认为第1层树为n叉，第2层树为n-1叉，直到第n层，只剩下1叉，即该路线被视为一种排列。即每往下一层，认为从该数组中"删去"一个数(上层的结点)，求剩下的数构成的"新数组"的全排列。 但是当数组中出现重复数字时这样写存在冗余，我们可以观察到，在每一层中，如果后一个数与前一个数一样的话，那么其接下来的分支也是一样的，所以应当删去，因此还采取像子集2那样的思路，判断每一层分支下nums[i]与nums[i-1]是否相等，不相等则递归。 但是这里的下标i-1的含义有些不一样，因为全排列的话，我们不考虑已加入到track数组的数，需要考虑的是新数组，即原数组nums中间可能有些值不作为结点考虑：nums[i-1]可能已加入到track数组中了，不需考虑，其真实前一个结点应是nums[i-2]或者更靠前的别的值。因此我们需要记录这个前结点进行比对：引入pre变量。 以上考虑的前提：数组nums有序，才能保证nums[i]和nums[i-1]比对

#include <bits/stdc++.h> using namespace std; int len; vector<int> track; int nums[100],vis[100];//全局变量，默认初始化为0 void dfs(int dep) { if(dep==len){ for(int i=0;i<len;i++) cout<<track[i]<<" "; cout<<endl; return ; } for(int i=0,pre=-1;i<len;i++) //初始时每个结点的孩子的第一个结点不需考虑，设为-1 if(vis[i]==0) //每个结点的第一个孩子结点之后的结点需要和前一个比对 if(pre==-1||nums[i]!=nums[pre]){ track.push_back(nums[i]); vis[i]=1; dfs(dep+1); track.pop_back(); vis[i]=0; pre=i;//记录下来 } } int main() { cin>>len; for(int i=0;i<len;i++) cin>>nums[i]; sort(nums,nums+len);//前提，要有序 dfs(0); return 0; }