题解 | #没有重复项数字的所有排列#

题目描述:给出一组数字，返回该组数字的所有排列
例如：
        [1,2,3]的所有排列如下
        [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

示例1
        输入：[1,2,3]
        返回值：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路：和字符串的全排列一样，简单直接递归，既然没有重复项的数字，每一项就各不相同，那么每一项都可以作为开头，然后求得剩余n-1个的所有排列，将作为开头的一项再加入到剩余n-1个的所有排列中即可，具体代码如下。
         1，permute(2,3,4,...,n)
        2，permute(1,3,4,...,n)
        3，permute(1,2,4,...,n)
        i，permute(1,2,...,i-1,i+1,...,n)
        n，permute(1,2,...,n-1)

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > RES;
        int n = num.size();
        if(n == 1)
        {
            vector<int> res;
            res.push_back(num[0]);
            RES.push_back(res);
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                vector<int> num1;
                for(int j=0;j<n;j++)
                {
                    if(j != i)
                    {
                        num1.push_back(num[j]);
                    }
                }
                vector<vector<int> > temp = permute(num1);
                num1.clear();
                for(int k=0;k<temp.size();k++)
                {
                    num1.push_back(num[i]);
                    for(int l=0;l<temp[k].size();l++)
                        num1.push_back(temp[k][l]);
                    RES.push_back(num1);
                    num1.clear();
                }
            }
        }
        return RES;
    }
};