Permutations - Video Solutions

Problem Overview: Given an array of distinct integers, return every possible ordering of those numbers. Each ordering is a permutation. The result must include all n! permutations where n is the array length.

Approach 1: Backtracking (O(n! * n) time, O(n) space)

This is the standard solution expected in interviews. Use backtracking to build permutations incrementally. Start with an empty path, iterate through the array, and choose a number that has not been used yet. Add it to the current path, recurse, then remove it during backtracking to explore the next option.

The key insight is treating permutation generation as a decision tree. At each level you pick one unused element. A boolean visited array or swapping technique ensures each element appears only once in a permutation. Because each permutation has length n and there are n! permutations, the total work is O(n! * n). The recursion stack and auxiliary arrays use O(n) space.

This approach works naturally with problems involving arrays and recursive exploration. It is easy to modify for variants such as permutations with duplicates or permutations with constraints.

Approach 2: Iterative Permutation Generation (O(n! * n) time, O(n! * n) space)

Permutations can also be generated iteratively without recursion. Start with a list containing an empty permutation. For each number in the input array, insert it into every possible position of every existing permutation. If the current permutation length is k, inserting the next number creates k + 1 new permutations.

This approach repeatedly expands the permutation list until all elements are used. For example, starting with [ ], inserting 1 produces [1]. Inserting 2 into every position of [1] gives [2,1] and [1,2]. Continue the process for each element until the permutations reach length n.

The time complexity remains O(n! * n) because every permutation must still be constructed and copied. Space complexity grows to O(n! * n) since all permutations are stored during generation. This approach avoids recursion and can feel more intuitive when thinking in terms of incremental construction.

Recommended for interviews: The backtracking solution is what most interviewers expect. It demonstrates control over recursion, state management, and search-space pruning. The iterative insertion approach still works and shows algorithmic creativity, but backtracking is the most common pattern for permutation and combination problems.