两种方法

第一种方法

利用回溯和递归，依次遍历数组，按照顺序提取数字，同时使用visited数组记录是否已经使用。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> tmp;
    
    void backtrack(vector<int> &num,int n,int length,vector<int>& visited){
        // num 数组  
        // n 回溯的位置
        if(n==length){ //  回溯结束条件
            result.push_back(num);
            return;
        }

        
        // 遍历提取
        for(int i=0;i<length;++i){
            if(visited[i]==1) continue;  // 只能选一次
            visited[i] = 1;
            tmp.push_back(num[i]);
            backtrack(num,n+1,length,visited);
            tmp.pop_back();
            visited[i]=0;
        }
        
    }
public:
    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<int> visited(num.size(),0);  
        // 回溯 + 递归
        backtrack(num,0,num.size(),visited);
        
        return result;
    }
};

第二种方法

全排列问题 只要转换数组中元素的位置即可

class Solution {
private:
    vector<vector<int>> result;
    
    void backtrack(vector<int> &num,int n,int length){
        // num 数组  
        // n 回溯的位置
        if(n==length){ 
            result.push_back(num);
            return;
        }
        // 横向遍历
        for(int i=n;i<length;++i){
            swap(num[i],num[n]);
            backtrack(num,n+1,length); // 递归
            swap(num[i],num[n]); // 回溯
        }
        
    }
public:
    
    vector<vector<int> > permute(vector<int> &num) {
        // 回溯 + 递归
        backtrack(num,0,num.size());
        
        return result;
    }
};