Permutations – Leetcode Solution

In this post, we are going to solve the 46. Permutations problem of Leetcode. This problem 46. Permutations is a Leetcode medium level problem. Let’s see the code, 46. Permutations – Leetcode Solution.

Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

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]]

Example 2 :


Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3 :


Input: nums = [1]
Output: [[1]]

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Now, let’s see the code of 46. Permutations – Leetcode Solution.

Permutations – Leetcode Solution

46. Permutations – Solution in Java

class Solution {
    
    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    public void allPermutation(int[] nums, List<List<Integer>> ans, int index){
        if(index >= nums.length){
            List<Integer> a = new ArrayList<>();
            for(int e : nums){
                a.add(e);
            }
            ans.add(a);
            return;
        }
        
        for(int i=index; i<nums.length ;i++){
            swap(nums,index,i);
            allPermutation(nums,ans,index+1);
            swap(nums,index,i);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        allPermutation(nums,ans,0);
        return ans;
    }
}

46. Permutations – Solution in C++

class Solution {
public:
    vector<vector<int>> ans;
    
    void f(vector<int> &nums, int idx){
        if(idx==nums.size()){
            ans.push_back(nums);
            return;
        }
        
        for(int i=idx;i<nums.size();i++){
            swap(nums[i],nums[idx]);
            f(nums,idx+1);
            swap(nums[i],nums[idx]);
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        f(nums,0);
        return ans;
    }
};

46. Permutations – Solution in Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def recursive(n, res = [], perms = []):
            if not n:
               res.append(perms[:])
            for i in range(len(n)):
                new_perm = n[:i] + n[i + 1:]
                perms.append(n[i])
                recursive(new_perm, res, perms)
                perms.pop()
            return res
        return recursive(nums)

Note: This problem 46. Permutations is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *