Using Backtracking


  • 0
    C

    Idea is as follow:

    1. Take each position, and swap other positions of the vector w.r.t current position.
    2. Push the swapped vector to the solution vector.
    3. Use recursion with position+1 as position now.
    4. Return if position = vector size.
    5. To do backtracking swap the same elements back again, which will give us the vector before the previous swap.
    void rec(vector<vector<int>> &sol, vector<int> &elem, int pos1, vector<int> &nums){
        
        if(pos1>=nums.size()){
            sol.push_back(elem);
            return;
        }
        
        for(int i=pos1;i<nums.size();i++){
            swap(elem[pos1],elem[i]);
            rec(sol,elem,pos1+1,nums);
            swap(elem[i],elem[pos1]);                      //backtracking
        }
    }
    
    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            
            vector<vector<int>> sol;
            vector<int> elem=nums;
            
            rec(sol,elem,0,nums);
            sort(sol.begin(),sol.end());        //to get the desired permutation w.r.t position
            return sol;
            
        }
    };
    

Log in to reply
 

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