题意

有一组无重复项的数字，求出其所有全排列。

思路

要求全排列，我们可以利用回溯算法，例如，假设当前已经求出了一个排列，则只要回溯到填入上两个数字的状态即可以得到一个新的排列，这样不停回溯就可以求出所有全排列。 代码如下：

class Solution {
public:
    vector<vector<int> > ans;//存储答案用数组
    bool used[10];//判断某个数字是否被使用过
    int N;//数字个数
  	void dfs(vector<int> a,vector<int> &num)
    {
        if(a.size()==N){ans.push_back(a);return;}//若求出了一个排列将其存入答案
        for(int i=0;i<N;i++)
        {
            if(!used[i]) //若未使用过n号数字
            {
                used[i]=true;
                a.push_back(num[i]);//将n号数字放入排列
                dfs(a,num);
                a.pop_back();
                used[i]=false;//回溯
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num)
    {
        memset(used, false, sizeof used);
        N=num.size();
        dfs(vector<int>(),num);//开始搜索
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n!)O(n!)$，为全排列个数。

空间复杂度：$O(n!)O(n!)$，为存储答案所用空间。