Leetcode46全排列DFS

链接
题目大意：给定一个数组，求出所有的全排列。
分析
DFS和回溯的方法。
回溯算法的核心
选择列表：表示当前可做的选择
路径：记录做过的选择
结束条件：遍历到树的底层，在这里是选择列表为空的时候。
回溯的代码框架

result=[]//存放结果 def backtrack(路径，选择列表){if 满足结束条件：result.add(路径)for 选择 in 选择列表：做选择backtrack(路径，选择列表);撤销选择}

全排列回溯解法：
分析
路径：track表示路径，也就是已经做出的选择。
选择列表：nums中哪些不在track中的元素，这里需要使用judge数组。

judge用来排除不合法的选择，也就是判断nums【i】是否已经出现在track中，如果出现过，就不能添加到路径，因为全排列没有重复的元素。false表示未进入到track中。

结束条件：nums中元素个数和track中元素个数相等。

class Solution { public:vector<vector<int> > result;vector<vector<int>> permute(vector<int>& nums) {vector<int> track;vector<bool> judge(nums.size(),false);//false表示未进入trackDFS(nums,track,judge);return result;}void DFS(vector<int> &nums,vector<int> &track,vector<bool> &judge){//exitif(nums.size()==track.size()){result.push_back(track);return;}for(int i=0;i<nums.size();i++){//make choice//怎么判断nums[i]在track里面if(judge[i])continue;track.push_back(nums[i]);judge[i]=true;DFS(nums,track,judge);//recall choicetrack.pop_back();judge[i]=false;}} };

STL也提供了一种计算全排列的函数next_permutation
参考笔者的另一篇博文C++STL之next_permutation使用

直接用next_permutation来求解

class Solution { public:vector<vector<int>> permute(vector<int>& nums) {if(nums.size()==0) return {};sort(nums.begin(),nums.end());//从小到大排序vector<vector<int>> tmp;//结果数组do{tmp.push_back(nums); //添加到结果数组中 }while(next_permutation(nums.begin(),nums.end()));//如果还有字典序更大的排列的话return tmp;} };

总结

以上是生活随笔为你收集整理的Leetcode46全排列DFS的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。