Permutations

The Permutations problem is a classic in coding interviews, combinatorics, and algorithm design. On the surface, it sounds simple: “list all possible orderings of a set of numbers.” But once you consider how many such orderings exist, how to generate them without omission or duplication, and how to do it efficiently, you realize this problem is really about structured exploration of a search space.

It’s a foundational exercise in recursion, backtracking, and state management.

Problem

You are given an array of distinct integers, nums. Your goal is to generate all possible permutations of these integers. A permutation is any arrangement of all elements where order matters.

You must return a list of all permutations. The order of the permutations in your output does not matter, but:

• Each permutation must contain every element from nums exactly once.
• No duplicate permutations should appear.

Example

A few important observations:

• A list of length \( n \) has exactly \( n! \) permutations.
• As \( n \) increases, \( n! \) grows extremely fast; therefore, any correct solution must at least output all permutations.
• The challenge is to generate them cleanly, without repetition, and in a structured manner.

Solution

The essential idea is backtracking: you build each permutation one element at a time, exploring all possible choices at each step, and undoing choices as you return from recursion.

Key idea

Think of constructing each permutation in n steps:

1. At each position, choose one unused number.
2. Add it to the current path.
3. Recurse to fill the next position.
4. When all numbers are used, you’ve formed a complete permutation.

This naturally forms a decision tree:

• Depth = n (one level per position in the permutation).
• Branching factor = number of remaining available numbers.
• Leaf nodes = complete permutations.

Why backtracking works

Backtracking ensures:

• You explore every valid ordering.
• You never reuse numbers already placed.
• You systematically undo choices to explore new paths.

Because each decision level considers all unused elements, you cover the entire permutation space with no duplicates.

Complexity

• Time: \( O(n * n!) \) — generating each of the \( n! \) permutations of size \( n \).
• Space:
  • \( O(n) \) recursion depth and path storage.
  • \( O(n * n!) \) for the result list.

Algorithm outline

1. Keep a list path representing the current partial permutation.
   
2. Maintain a used array indicating which numbers are already chosen.
   
3. When path has length \( n \), add it to the result.
   
4. Otherwise, for each index i:
   
   • If nums[i] is unused, choose it.
   • Recurse.
   • Undo the choice.

Sample implementation (Python)

Example usage

Alternative in-place method (swap-based)

Another common approach fixes elements in-place:

• At recursion level pos, swap any element from [pos, n-1] into position pos.
• Recurse on pos + 1.
• Swap back afterward.

This avoids a used array and often performs better in low-level languages, though the conceptual flow is identical: choose → recurse → undo.

Interview insight

The Permutations problem is a gateway to understanding backtracking. Once you master this pattern, you are ready for more advanced variants:

• Permutations with duplicates
• Lexicographical next permutation
• Constraint-based permutation generation

All of them rely on the same recursive choice-and-undo pattern you’ve learned here.