Coding Interview Questions | Permutations

January 24th, 2024

Permutations Problem Introduction:

This summary will talk about my solution to the permutations problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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

How do you solve the Permutations Problem using Recursion?

Solution:

function permute(nums: number[]): number[][] {
  const permutations: number[][] = [];
  const generatePermutations = (currentPermutation: number[]) => {
    if (currentPermutation.length === nums.length) {
      permutations.push([...currentPermutation]);
      return;
    }

    for (let idx = 0; idx < nums.length; idx++) {
      const num = nums[idx];
      if (!currentPermutation.includes(num)) {
        currentPermutation.push(num);
        generatePermutations(currentPermutation);
        currentPermutation.pop();
      }
    }
  };

  generatePermutations([]);

  return permutations;
}

Permutations Solution Summary:

Below is a breakdown of the key aspects of the solution for the problem seen above:

  1. Backtracking Approach: The algorithm employs a backtracking strategy to explore all possible permutations systematically.

  2. Permutations Array: The permutations array stores all the generated permutations.

  3. Recursive Permutation Generation: The generatePermutations function is a recursive function that explores and generates permutations by appending the current permutation if a permutation has been explored that matches the length of the input array, and backtracking otherwise.

  4. Base Case: The base case checks if the current permutation’s length equals the length of the input nums. If true, the permutation is complete and added to the permutations array.

  5. Avoiding Duplicates: During the exploration, the algorithm avoids duplicates by checking if a number is already present in the current permutation before including it.

Complexities

  1. Time Complexity: The time complexity is influenced by the number of permutations generated. In the worst case, the algorithm explores all possible permutations, resulting in a time complexity of O(N!), where N is the length of the input array.

  2. Space Complexity: The space complexity is also determined by the number of permutations. The permutations array contributes to the space complexity, resulting in O(N!) space, where N is the length of the input array. Additionally, the recursive call stack contributes to the space complexity.