Leetcode 46. Permutations

Problem Statement —
Given an array nums of distinct integers, return all the possible permutations.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Here we will be using the recursive approach to solve this problem, it is a backtracking problem in which we have to check whether a particular element has already been taken or not in each particular case.

In this, we are recursively calling the permute(int[] nums) method which will return a List of all permutations.
We are using Java language to solve this, but the approach will be common for all programming languages.

Let’s go step by step -

1. First check if the array nums contain more than 1 element, if not then convert it into ArrayList and return it, if yes, then proceed to the next step.
2. We are converting the array into ArrayList(arr) for better handling of elements( to easily add and remove elements from array)
3. Now we will start looping into ArrayList for each element -
   3.1 Remove the first element of ArrayList and assign it to a variable n
   3.2 Now send the remaining ArrayList in the form of an array to the permute function. Which will do the permutations of the rest of the array till a single element and send back all permutations which we will store in a variable r.
   3.4 For each of the permutations in r , append the variable n to it in the last so that all elements are there.
   3.5 Now add all the permutations to the result and add n back toarr in the last to make it complete ArrayList again.
   3.6 Now do it for the next element of arr till all combinations are there.
4. Now return the result.

Here is my solution in Leetcode.

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        if(nums.length==1){
            List<Integer> values = new ArrayList<>();
            values.add(nums[0]);
            List<List<Integer>> r = new ArrayList<>();
             r.add(values);
             return r;
        }
        List<Integer> arr = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            arr.add(nums[i]);
        }
        for(int i=0;i<arr.size();i++){
            int n = arr.get(0);
            arr.remove(0);
            int[] n1 = new int[arr.size()];
            for(int j=0;j<arr.size();j++){
                n1[j]=arr.get(j);
            }
            List<List<Integer>> r = permute(n1);
            for(List<Integer> per : r){
                per.add(n);
                result.add(per);
            }
            arr.add(n);
            
        }

        return result;
    }
}

Happy Coding!!!
Do clap if you like the blog.
Any queries or suggestions? Sure!! Ping me :
* LinkedIn
* Twitter
* GitHub
* Medium