一道permutation的题求教～～～～

小弟最近在转cs刷leetcode，碰到permutation这题了。。 （不是permutation 2 ,仅仅只是1 ）原题是给你一串int（没有重复），找出它的所有全排列。 例如给出 1，2，3， 就要返回（1，2，3），（1，3，2），（2，1，3），（2，3，1），
（3，1，2），（3，2，1）


recursive看得有点懵逼。。。 实际上我最怕碰到loop里面套recursive的了，根本不知道它在干嘛啊。

先贴上别人的代码吧：（c++）

class Solution {

public:

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

        vector<vector<int>> res;

        create(nums,res,0);

        return res;

    }

    void create(vector<int>& nums,vector<vector<int>> &res,int n)

    {

        if(n==nums.size()-1)

            res.push_back(nums);

        else

        {

            for(int i=n;i<nums.size();i++)

            {

                swap(nums[i][i],nums[n]);[/i]

[i]                create(nums,res,n+1);[/i]

[i]                swap(nums[i][i][i],nums[n]);[/i][/i][/i]

[i][i]            }[/i][/i]

[i][i]        }[/i][/i]

[i][i]    }[/i][/i]

[i][i]

    void swap(int &a,int &b)

    {

        int tmp=a;

        a=b;

        b=tmp;

    }

};

有哪位大神可以帮忙解释一下recursive在干嘛吗。。 还有能顺便说一下碰到此类问题应该如何写递归吗，真心对这种题很无语啊。。

[/i][/i]

代码写错了吧，swap里面参数应该是nums[i]..

luofeidream 发表于 2016-2-12 10:44
代码写错了吧，swap里面参数应该是nums..

哦哦对的。。。 应该是粘贴的时候出了点问题，已经改正了，谢谢提醒！

JEM 发表于 2016-2-12 12:36
哦哦对的。。。 应该是粘贴的时候出了点问题，已经改正了，谢谢提醒！

这个recursive的意思是每次换一个“头”，然后递归的把剩余的所有元素的permutation加到这个“头”后面，比如1 2 3，先产生1 2 3， 然后 2 3里面把“头”换成3，产生1 3 2， 接着把1 换成2产生2 1 3 2 3 1等等……

luofeidream 发表于 2016-2-12 12:40
这个recursive的意思是每次换一个“头”，然后递归的把剩余的所有元素的permutation加到这个“头”后面， ...

能不能麻烦你讲一下两个swap放在那是在干嘛啊？ 还有就是recursive为什么要放在两个swap中间？

JEM 发表于 2016-2-12 15:34
能不能麻烦你讲一下两个swap放在那是在干嘛啊？ 还有就是recursive为什么要放在两个swap中间？

首先想清楚create这个方法是算出所有nums从第n位到最后一位的全排列。
在create方法中，我们拿第一层递归n=0，以及i=1的情况举例，它的做法是先把1和2换位，然后递归求出1，3的全排列，然后把1换回原位好在下个循环和3换位。

excellent5 发表于 2016-2-12 16:15
首先想清楚create这个方法是算出所有nums从第n位到最后一位的全排列。
在create方法中，我们拿第一层递 ...

这样说的话可不可以这么理解，就拿第一层递归的那一个for loop来说，先是1和自己换，求后面的全排列，然后1和2换，2作为第一个数，求一次全排列，然后求完换回来，然后1和3换，3作为第一个数，求一次全排列。所以这样1，2，3作为第一个数的所有全排列就都求出来了。 是这样理解吗？

JEM 发表于 2016-2-13 11:13
这样说的话可不可以这么理解，就拿第一层递归的那一个for loop来说，先是1和自己换，求后面的全排列，然 ...

嗯，我认为就是这样的