Permutations

O(n!) — Factorial Time

syntax

Generating all permutations of n items. Grows astronomically fast.

example

// JavaScript
function permutations(arr) {
  if (arr.length <= 1) return [arr];
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const perm of permutations(rest)) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

# Python
def get_permutations(arr):
    if len(arr) <= 1:
        return [arr[:]]
    result = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for perm in get_permutations(rest):
            result.append([arr[i]] + perm)
    return result

output

Time: O(n!) | Space: O(n!) to store all permutations

Note 10! = 3,628,800 and 20! is over 2 quintillion. If n > ~10-12, factorial algorithms won't finish in time. The traveling salesman brute force is O(n!). Interviewers accept factorial only when generating all permutations is required.

Permutations

DSA · Recursion & Backtracking

syntax

Generate all orderings of elements.
Backtrack: at each position, try each unused element.
Swap or use a 'used' boolean array to track which elements are placed.

example

// JavaScript
function permute(nums) {
  const result = [];
  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop(); // undo choice
    }
  }
  backtrack([], nums);
  return result;
}

# Python
def permute(nums):
    result = []
    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    backtrack([], nums)
    return result

output

permute([1,2,3]) → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Note Time O(n! * n), Space O(n). The 'undo choice' step (current.pop()) is the hallmark of backtracking. For permutations with duplicates: sort first, and skip if nums[i] == nums[i-1] and nums[i-1] was not used in this branch. n! grows extremely fast — practical only for n ≤ ~10.

DSAInterview Prep