LeetCode:Permutations(求全排列)-白红宇

LeetCode:Permutations(求全排列)

阅读量：4655 次

发布时间：2019-06-09

本文共 2487 字，大约阅读时间需要 8 分钟。

Given a collection of numbers, return all possible permutations.

For example,

[1,2,3] have the following permutations:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

思路：将元素一个一个的插入，首先只有一个元素{1}，此时，插入之后会的到两个vector<int>，{1,2}，{2,1}，然后继续插入第三个元素3，会得到{3,1,2}，{1,3,2}，{1,2,3}和{3,2,1}，{2,3,1}，{2,1,3}。

依次类推，将所有的元素插入其中。

C++代码实现：

#include
     
      #include
      
       using namespace std;class Solution {public:    vector
       
        
          > permute(vector
         
           &num) {        if(num.empty())            return vector
          
           
             >(); vector
            
             
               > ret{ {num[0]}}; size_t i,j,k; for(i=1;i

temp1; vector

> temp2=ret; ret.clear(); for(j=0;j

vec={ 1,2,3,4}; vector

> result=s.permute(vec); for(auto a:result) { for(auto v:a) cout<

<<" "; cout<

运行结果：

方法二，使用回溯的方法。

#include
     
      #include
      
       using namespace std;class Solution {public:    vector
       
        
          > permute(vector
         
           &num) {        if(num.empty())            return vector
          
           
             >(); vector
            
             
               > ret{ {num[0]}}; size_t i,j,k; for(i=1;i

temp1; vector

> temp2=ret; ret.clear(); for(j=0;j

vec={ 1,2,3,4}; vector

> result=s.permute(vec); for(auto a:result) { for(auto v:a) cout<

<<" "; cout<

方法三：利用递归的方法(递归-恢复-递归-恢复)

首先解释下全排列怎么生成的，看懂后代码就好写了。例如123，有6种排列方式，这其中有个规律，用第一个数字从前往后与所有数字交换(包括第一个数字本身)，每次交换都确定一个位置。

123——最左边的数字确定了——中间的数字确定了

|——123(交换1与1所得)——132(交换2与3所得)——确定最右边的位置，就剩下一位了，肯定确定了。

|——213(交换1与2所得)——231———————— 同上

|——321(交换1与3所得)——312———————— 同上

去除重复的全排列也很简单，例如：

数字序列1232，交换1与第一个2，得(2)132，括号里的2固定了，递归处理后面132序列的全排

数字序列还是1232，交换1与最后一个2，得(2)231，括号里的2固定了，递归处理后面的231序列的全排

子序列132与231的全排肯定有重复的，这就是造成重复的原因

实现代码：

class Solution {public:    vector
     
      
        > permute(vector
       
         &num) {        vector
        
         
           > res;        sort(num.begin(),num.end());        helper(num,0,num.size()-1,res);        return res;    }    void helper(vector
          
            &num,int start,int end,vector
           
            
              > &res) { if(start==end) { res.push_back(num); } else { for(int i=start;i<=end;i++) { swap(&num[start],&num[i]); helper(num,start+1,end,res); swap(&num[start],&num[i]); } } } void swap(int* a,int *b) { int tmp=*a; *a=*b; *b=tmp; }};