Permutations

Permutations

What is this problem about?

The Permutations problem asks you to return all possible permutations of a given array of distinct integers. This Permutations coding problem is the canonical backtracking problem — every backtracking algorithm builds on this fundamental template. The array and backtracking interview pattern is the most essential skill demonstrated here.

Why is this asked in interviews?

J.P. Morgan, Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it's the foundational backtracking problem. Every candidate is expected to implement this cleanly. It validates understanding of state management, recursive exploration, and result collection in backtracking.

Algorithmic pattern used

Backtracking with used array. Maintain a used boolean array and current list. At each recursive call: if len(current) == n, add a copy to results. For each index i from 0..n-1: if not used[i], mark used[i]=True, append arr[i], recurse, then unmark and remove (backtrack).

Example explanation

nums=[1,2,3]. Start backtrack from empty path.

• Pick 1: [1]. Pick 2: [1,2]. Pick 3: [1,2,3] → add. Backtrack to [1,2]. Pick 3→[1,3]... Result: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] (6 = 3! permutations).

Common mistakes candidates make

• Not making a copy when adding to results (list is shared and gets modified).
• Not restoring state (not removing the last element on backtrack).
• Using a seen set on values instead of used array on indices (doesn't work for duplicate values).
• Off-by-one in recursive depth check.

Interview preparation tip

Permutations is the backtracking archetype. Master the template: mark → explore → unmark. This pattern appears in: permutations, subsets, combinations, word search, N-queens, and dozens more. The copy-on-result is critical: always add a copy of current, not current itself. Practice implementing Permutations I, then II (with duplicates), then III (alternating), to build complete backtracking mastery.