Last updated on January 20th, 2025 at 04:12 am

Here, we see the Permutations LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Backtracking

Companies

Linkedin, Microsoft

Level of Question

Medium

Permutations LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique that involves exploring all possible solutions by building a solution incrementally and removing solutions that fail to satisfy the problem constraints.

In this case, the problem is to generate all permutations of a given list of numbers. The algorithm explores all possible arrangements of the numbers by recursively swapping or inserting elements and backtracking to explore other possibilities.

3. Code Implementation in Different Languages

3.1 Permutations C++

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> results;
        generatePermutations(0, &nums, &results);
        return results;
    }
private:
    void generatePermutations(int i, vector<int>* nums_ptr, vector<vector<int>>* results) {
        auto& nums = *nums_ptr;
        if (i == nums.size() - 1) {
            results->emplace_back(nums);
            return;
        }
        for (int j = i; j < nums.size(); ++j) {
            std::swap(nums[i], nums[j]);
            generatePermutations(i + 1, nums_ptr, results);
            std::swap(nums[i], nums[j]);
        }       
    }
};

3.2 Permutations Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> permutations = new ArrayList<>();
		if (nums.length == 0) {
			return permutations;
		}
		collectPermutations(nums, 0, new ArrayList<>(), permutations);
		return permutations;
    }
	private void collectPermutations(int[] nums, int start, List<Integer> permutation,
 			List<List<Integer>>  permutations) {
		
		if (permutation.size() == nums.length) {
			permutations.add(permutation);
			return;
		}
		for (int i = 0; i <= permutation.size(); i++) {
			List<Integer> newPermutation = new ArrayList<>(permutation);
			newPermutation.add(i, nums[start]);
			collectPermutations(nums, start + 1, newPermutation, permutations);
		}     
    }
}

3.3 Permutations JavaScript

var permute = function(nums) {
  let results = [];

  let permutations = (current, remaining) => {
    if(remaining.length <= 0) results.push(current.slice());
    else {
      for(let i = 0; i < remaining.length; i++) { // Loop through remaining elements
        current.push(remaining[i]); // Insert the iTH element onto the end of current
        permutations(current.slice(), remaining.slice(0, i).concat(remaining.slice(i+1))); // Recurse with inserted element removed
        current.pop(); // Remove last inserted element for next iteration
      }
    }
  };
  permutations([], nums);
  return results;  
};

3.4 Permutations Python

class Solution(object):
    def permute(self, nums):
        res = []
        self.dfs(nums, [], res)
        return res
    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
        for i in xrange(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * n!)	O(n!)
Java	O(n * n!)	O(n!)
JavaScript	O(n * n!)	O(n!)
Python	O(n * n!)	O(n!)

• Time Complexity:
  • The algorithm generates all permutations, which is O(N!) for N elements.
  • For each permutation, O(N) operations are performed (e.g., swaps, insertions, or slicing).
  • Hence, the overall time complexity is O(N * N!).
• Space Complexity:
  • The space complexity is dominated by the storage of all permutations, which is O(N!) since there are N! permutations, each of size N.
  • Additionally, the recursion stack requires O(N) space for the depth of the recursion.
• Backtracking:
  • The algorithm explores all possible permutations by recursively building solutions and backtracking to explore other possibilities.