C++ 解法, 执行用时: 2ms, 内存消耗: 516KB, 提交时间: 2021-06-20

class Solution {
public:
    vector<vector<int>> res;
    vector<int> i_vec;   vector<bool> record;   int len;
    vector<vector<int> > permute(vector<int> &num) {
        res.clear();   len = num.size();
        record = vector<bool>(len, false);
        DFS(num, 0);
        
        return res;
    }
    
    void DFS(vector<int> &arr, int idx)
    {
        if(idx == len){ res.push_back(i_vec);   return ; }
        
        for(int i=0; i<len; i++){
            if( record[i] ) continue;
            record[i] = true;   i_vec.push_back( arr[i] );
            
            DFS(arr, idx+1);
            
            record[i] = false;   i_vec.pop_back();
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 540KB, 提交时间: 2021-09-12

class Solution {
    private:
        vector<int>path;
        vector<vector<int>>Res;
        void Dfs(vector<int> &num, vector<bool>& Visited)
        {
            if(path.size() == num.size())
            {
                Res.push_back(path);
                return;
            }
            for(int i = 0; i < num.size(); i++)
            {
                if(!Visited[i])
                {
                    path.push_back(num[i]);
                    Visited[i] = true;
                    Dfs(num, Visited);//结果达到要求，则退出该层。
                    Visited[i] = false;//该层置为false
                    path.pop_back();//很关键！！！，要记得回溯！！！
                }
            }
     }
    
public:
    vector<vector<int> > permute(vector<int> &num) {
        if(num.size() == 0)
        {
            return {};
        }
        vector<bool>Visited(num.size(), false);
        Dfs(num, Visited);
        return Res;
    }
};

C 解法, 执行用时: 3ms, 内存消耗: 436KB, 提交时间: 2021-08-18

int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    int i,j,k,l,a,temp;
    int n=1,layer=0,flag=0;
    for (i=2;i<=numLen;i++)
    {
        n=n*i;
    }
    int **res= (int **)malloc(n*sizeof(int*));
    for (i=0;i<n;i++)
    {
        res[i]=(int *)malloc(numLen*sizeof(int*));
    }
    int used[numLen];
    int now[numLen];
    for (i=0;i<numLen;i++)
    {   
        used[i]=i;
        res[0][i]=num[used[i]];
    }
    *returnSize=0;
    *returnColumnSizes =(int *)malloc(n* sizeof(int));
    for (i=0;i<n;i++)
    {
         (*returnColumnSizes)[*returnSize]=numLen;
         (*returnSize)++;
    }
    i=1;
    for (i=1;i<n;i++)
    {
        for (j=numLen-2;j>=0;j--)
        {
            for (l=numLen-1;l>j;l--)
            {
                if(used[l]>used[j])
                {
                    memcpy(now, used, sizeof(int)*j);
                    memcpy(now+j, used+l, sizeof(int)*(numLen-l));
                    memcpy(now+j+numLen-l, used+j, sizeof(int)*(l-j));
                    flag=1;
                    break;
                }
            }
            if (flag==1)
            {
                 break;
            }
            
        }
        for (j=0;j<numLen;j++)
                 {   
                      res[i][j]=num[now[j]];
                 } 
                memcpy(used, now, sizeof(int)*numLen);
                flag=0;
    }
        
       
    return res;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 452KB, 提交时间: 2020-08-28

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> res;
        getAll(res,num,0);
        return res;
    }
    void getAll(vector<vector<int>>& res,vector<int>& num,int start)
    {
        if(start == num.size()-1)
        {
            res.push_back(num);
            return ;
        }
        for(int i=start;i<num.size();i++)
        {
            swap(num[i],num[start]);
            getAll(res,num,start+1);
            swap(num[i],num[start]);
        }
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 456KB, 提交时间: 2020-10-30

class Solution {
public:
    vector<vector<int>> permute(vector<int> &num) {
		int n = num.size();
		vector<vector<int>> res;
        if(n == 0)
            return res;
		dfs(num,res,n,0);
		return res;
    }
	void dfs(vector<int> &num,vector<vector<int>>& res,int n,int pos)
	{
		if(pos > n)
            return;
        if(pos == n)
			res.push_back(num);
		else
		{
			for(int j = pos;j < n;j++)
			{
				if(num[j] == num[pos] && j != pos)
					continue;
				swap(num[pos],num[j]);
				dfs(num,res,n,pos+1);
				swap(num[pos],num[j]);
			}
		}
	}
};