Leetcode 46 Permutations Solutions

Problem Statement could be found @https://leetcode.com/problems/permutations/

class Solution {
   
    vector<vector<int>> retvec;
public:

void swap(vector<int> &nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void helper(vector<int> &nums, int index){
    if (index == nums.size()){
        retvec.push_back(nums);
        return ;
    }
    for (int i=index; i< nums.size();i++){
       
        swap(nums, i, index);
        helper(nums, index+1);
        swap(nums, i, index);
    }
   
}
    vector<vector<int>> permute(vector<int>& nums) {
       
        helper(nums,0);
        return retvec;
    }
};

Leetcode 31 : Next Permutation Solution

Problem Statement could be found @https://leetcode.com/problems/next-permutation/

Approach-
There are 2 ways to solve this problem:

Way 1:
1. Find all permutations,then sort them.
2. Search for the input permutation and then select the next one

Way 2:
Let us understand this by an example. Assume the input is
2, 5,4,1

If we start from the last element  can we put 1 anywhere to get a larger permutation.
Answer is No
Now lets analyze 2nd element, can we put it anywhere to get a larger permutation.
Answer is Yes. We can swap it with 2 and get a larger permutation.
But is it the next largest of input ? No. But it moves us in the right direction
If we swap, then our input would be 4,5,2,1
Here we if we sort elements except 4 then we get our answer.Which would be 4,1,2,5

But how do we fix on 4 to be swapped? So lets look another time & try to refine.

Can we swap (1 and 4) to get a higher perm?
No
Can we swap (4 and 5) to get a higher perm?
No
Can we swap (2 and 5) to get a higher perm?
Yes. But it won't give the result.
Only thing it tells is 2 is eligible candidate for removal.Why?
Because there is at least one larger element on right side. Now how do we find ideal candidate?

The definition of ideal candidate is "Smallest element on the right side which is larger than 2".
Once you find the ideal candidate swap it with 2. Swapping would ensure left seq till 2 are in order.
Now you have to only worry about getting smallest sequence on right of 2. How do we get it?
Use sorting:)

Following is the code for it


Code Snippet:

class Solution {
public:

void swap(vector<int> &nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] =temp;
 
}
 int getElementIndex(vector<int> &nums,int val,int index){
    int minVal = nums[index];
    int minIndex =index;
    while (index < nums.size()){
        if ((nums[index] > val) &&(minVal > nums[index])){
            minVal = nums[index];
            minIndex = index;
           
        }
        index ++;
       
    }
    return minIndex;
 }
   
    void nextPermutation(vector<int>& nums) {
        for (int i=nums.size()-1;i>0;i--)    {
            if (nums[i-1] < nums[i]){
                int index =getElementIndex(nums,nums[i-1],i);
                swap(nums, index,i-1);
                sort(nums.begin()+i,nums.end());
                return ;
            }
        }
        sort(nums.begin(),nums.end());
    }
};