[backtracking] Clean C++ recursion with detailed explanation


  • 0

    The idea is much like the insertion sort. We start with only the first number, and pick next number from the rest of array, insert it to the front or back position of the first number, and pick the third number, insert it to front or mid or back position of the [first, second] array, and so on, until no element left.
    For example, given array [1,2,3].
    First, we have [1] as array to be inserted, and [2,3] remain;
    next number is 2, we insert it to the front or back of [1], which become [1,2] and [2,1], with [3] remain.
    Then we pick number 3, insert it to [1,2] and [2,1],
    Insert to front position, we get
    [3,1,2],
    [3,2,1]
    Insert to mid position, we get
    [1,3,2],
    [2,3,1],
    Insert to back, we get
    [1,2,3],
    [2,1,3],
    and no element left in remain array, finish.
    Here is my code,

        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int>>res;
            if(nums.size()==0) return res;
            vector<int>vec(1,nums[0]);
            backtrack(nums,1,vec,res);
            return res;
        }
        
        void backtrack(vector<int>& nums, int pos, vector<int>& vec, vector<vector<int>>& res){
            if(pos==nums.size()){
                res.push_back(vec);
                return;
            }
            for(int i=0;i<=vec.size();i++){
                vec.insert(vec.begin()+i,nums[pos]);
                backtrack(nums,pos+1,vec,res);
                vec.erase(vec.begin()+i);
            }
            return;
        }
    

Log in to reply
 

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