Easy to understand C++ solution (DFS+backtracking)


  • 0
    L
    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int> > result;
            int n=nums.size();
            if(n==0) return result;
            vector<int> path;
            vector<int> mark(n,0); \\mark[i]=0 means nums[i] has not been used yet
            DFS(result,path,nums,mark,n);
            return result;
        }
        
        void DFS(vector<vector<int> >&result,vector<int> path,vector<int>&nums,vector<int> &mark,int n){
            if(path.size()==n){
                result.push_back(path);
                return;
            }
            for(int i=0;i<n;i++){
                if(!mark[i]) {
                    path.push_back(nums[i]);
                    mark[i]=1;
                    DFS(result,path,nums,mark,n);
                    path.pop_back();
                    mark[i]=0;
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.