LeetCode:Permutations(求全排列)

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<iostream>

#include<vector>

using namespace std;

class Solution {

public:

    vector<vector<int> > permute(vector<int> &num) {

        if(num.empty())

            return vector<vector<int> >();

        vector<vector<int> > ret{{num[]}};

        size_t i,j,k;

        for(i=;i<num.size();i++)

        {

            vector<int> temp1;

            vector<vector<int> > temp2=ret;

            ret.clear();

            for(j=;j<temp2.size();j++)

            {

                temp1=temp2[j];

                k=;

                while((temp1.begin()+k)!=temp1.end())

                {

                    temp1.insert(temp1.begin()+k,num[i]);

                    ret.push_back(temp1);

                    temp1=temp2[j];

                    k++;

                }

                temp1.push_back(num[i]);

                ret.push_back(temp1);

            }

        }

        return ret;

    }

};

int main()

{

    Solution s;

    vector<int> vec={,,,};

    vector<vector<int> > result=s.permute(vec);

    for(auto a:result)

    {

        for(auto v:a)

            cout<<v<<" ";

        cout<<endl;

    }

}

运行结果：

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

#include<iostream>

#include<vector>

using namespace std;

class Solution {

public:

    vector<vector<int> > permute(vector<int> &num) {

        if(num.empty())

            return vector<vector<int> >();

        vector<vector<int> > ret{{num[]}};

        size_t i,j,k;

        for(i=;i<num.size();i++)

        {

            vector<int> temp1;

            vector<vector<int> > temp2=ret;

            ret.clear();

            for(j=;j<temp2.size();j++)

            {

                temp1=temp2[j];

                k=;

                while((temp1.begin()+k)!=temp1.end())

                {

                    temp1.insert(temp1.begin()+k,num[i]);

                    ret.push_back(temp1);

                    temp1=temp2[j];

                    k++;

                }

                temp1.push_back(num[i]);

                ret.push_back(temp1);

            }

        }

        return ret;

    }

};

int main()

{

    Solution s;

    vector<int> vec={,,,};

    vector<vector<int> > result=s.permute(vec);

    for(auto a:result)

    {

        for(auto v:a)

            cout<<v<<" ";

        cout<<endl;

    }

}

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

首先解释下全排列怎么生成的，看懂后代码就好写了。例如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<vector<int> > permute(vector<int> &num) {

        vector<vector<int> > res;

        sort(num.begin(),num.end());

        helper(num,,num.size()-,res);

        return res;

    }

    void helper(vector<int> &num,int start,int end,vector<vector<int> > &res)

    {

        if(start==end)

        {

            res.push_back(num);

        }

        else

        {

            for(int i=start;i<=end;i++)

            {

                swap(&num[start],&num[i]);

                helper(num,start+,end,res);

                swap(&num[start],&num[i]);

            }

        }

    }

    void swap(int* a,int *b)

    {

        int tmp=*a;

        *a=*b;

        *b=tmp;

    }

};

巴特西

LeetCode:Permutations(求全排列)

最新文章

热门文章