Permutations

Learning to Explore Without Getting Lost

Permutations is one of those problems that looks intimidating until you realize it's really about controlled exploration. Interviewers use it to see whether you can reason about recursion, backtracking, and state management, and whether you can do it without losing track of where you are.

Problem Statement

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

Examples:

• [1, 2, 3] → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

• [1, 2] → [[1,2], [2,1]]

• [1] → [[1]]

1. Clarify Requirements Before Jumping Into Code

Before diving in, let's restate the rules to confirm understanding.

Input: An array of distinct integers.

Output: A list of all possible permutations, where each permutation uses every number exactly once.

Key clarifications to raise:

• If nums is empty, do we return an empty list or a list containing one empty permutation? Typically the latter. There's exactly one way to arrange zero elements.

• Are duplicates possible? The standard version says no. That simplifies things significantly; no need to deduplicate results.

• Does the order of results matter? No.

2. Identify the Category of the Problem

This is a backtracking problem: a specific pattern of depth-first search where you build a solution incrementally, explore it fully, and then undo your last choice before trying a different one.

The structure is always the same:

Choose → Explore → Un-choose

Once you recognize backtracking, the shape of the solution becomes predictable. The interesting parts are the details: what constitutes a "choice," how you track state, and how you know when you're done.

3. Start With Brute Force to Build Intuition

Is there even a brute-force alternative here? Not really. Any correct solution must enumerate all n! permutations, because that's how many there are. For [1, 2, 3] that's 6. For [1, 2, 3, 4] that's 24. Factorial growth is unavoidable given the problem's requirements.

What is avoidable is wasted work - revisiting the same partial states, or losing track of which elements have been used. That's what good structure gives us.

So rather than asking "can I go faster?", the right question is: "What's the clearest way to generate all permutations without making mistakes?"

4. Brainstorm More Solutions

Step 1: Think About How You'd Do This By Hand

Forget code for a moment. If someone asked you to list all permutations of [1, 2, 3] on paper, what would you do?

You'd probably pick a first number, then decide what comes second, then what comes third. Something like:

Start with 1:
  Then 2:  Then 3:  → [1, 2, 3]
  Then 3:  Then 2:  → [1, 3, 2]
Start with 2:
  Then 1:  Then 3:  → [2, 1, 3]
  Then 3:  Then 1:  → [2, 3, 1]
Start with 3:
  ...

This is actually a tree. At each level of the tree, you choose one number from whatever's left. When you've chosen all of them, you have a complete permutation. When you back up to try a different branch, you "un-choose" the last number and try the next one.

That's backtracking, and it maps directly to code.

Step 2: Define the Recursive State

What information does each recursive call need?

• The current path: numbers chosen so far, in order.

• Which numbers are available: which ones haven't been used yet.

At each step, we loop through all numbers. If a number hasn't been used, we:

1. Mark it used and add it to the path (choose)

2. Recurse (explore)

3. Remove it from the path and unmark it (un-choose)

When path.length == nums.length, we've placed every number. Record the permutation and return.

Let's trace this for [1, 2, 3]:

backtrack(path=[], used=[F,F,F])
  try 1 → backtrack(path=[1], used=[T,F,F])
    try 2 → backtrack(path=[1,2], used=[T,T,F])
      try 3 → backtrack(path=[1,2,3], used=[T,T,T])
        path is full → record [1,2,3]
      un-choose 3
    un-choose 2
    try 3 → backtrack(path=[1,3], used=[T,F,T])
      try 2 → backtrack(path=[1,3,2], used=[T,T,T])
        path is full → record [1,3,2]
      un-choose 2
    un-choose 3
  un-choose 1
  try 2 → backtrack(path=[2], used=[F,T,F])
    ...and so on

Notice what discipline this requires: every recursive call must leave the state exactly as it found it. If you add 1 to the path before recursing, you must remove it after. If you mark used[0] = true before recursing, you must mark it false after. The recursive call is allowed to temporarily modify state, but it must clean up before returning. This is the core discipline of backtracking.

You might wonder: why do we need a used array? Can't we just check whether the current number is already in path?

Technically yes, but it's O(n) per check. With n choices per level and n levels, that's O(n²) extra work per permutation. A boolean used array gives us O(1) lookup and makes the logic explicit.

Step 3: An Alternative - Swap-Based Permutation

Take another look at the path-based approach. At any point in the recursion, path contains the numbers we've chosen so far, and nums minus the used elements contains the numbers still available. We're essentially maintaining two lists - chosen and unchosen - and moving elements between them one at a time.

But do we actually need two separate data structures for this? What if we used nums itself to track both at once?

Here's the insight: if we say "everything to the left of index start has already been chosen, and everything from start onward is still available," then we can represent both lists within the same array. To place a number at position start, we swap it into that slot from somewhere in the remaining right portion. After recursing, we swap it back, restoring the "unchosen" pool exactly as we found it.

That leads to a swap-based approach where we never need a separate path or used array at all.

void backtrack(int[] nums, int start, List<List<Integer>> result) {
    if (start == nums.length) {
        // current nums array is a complete permutation
        List<Integer> perm = new ArrayList<>();
        for (int n : nums) perm.add(n);
        result.add(perm);
        return;
    }

    for (int j = start; j < nums.length; j++) {
        swap(nums, start, j);           // choose: put nums[j] at position start
        backtrack(nums, start + 1, result);  // explore
        swap(nums, start, j);           // un-choose: restore
    }
}

Trace through an example to verify correctness.

This approach is more space-efficient (no used array, no separate path) and slightly more elegant, but harder to explain under pressure and harder to adapt to variations. The path-based approach is easier to reason about and more transferable to related problems like Subsets and Combination Sum. Being able to consider the extendability of a solution is an important real-life skill and this could be an opportunity to showcase that skill to the interviewer.

5. Trade-Offs at a Glance

Approach	Time	Space	Notes
Path + used array	O(n × n!)	O(n)	Clear, transferable, preferred
Swap-based in-place	O(n × n!)	O(n)	More elegant; harder to adapt
Iterative generation	O(n × n!)	O(n!)	Avoids recursion; complex to implement

All correct approaches share the same time complexity - you can't escape n! output. The O(n) factor comes from copying each complete path. Space refers to the recursion stack, not the output.

6. Pseudocode

result = empty list
used = boolean array of size n, all false

backtrack(path):
    if path.length == nums.length:
        add a copy of path to result
        return

    for i from 0 to n-1:
        if used[i]:
            continue

        mark used[i] = true
        add nums[i] to path

        backtrack(path)

        remove last element from path
        mark used[i] = false

call backtrack with empty path
return result

The symmetry here is important: every line that modifies state before the recursive call has a mirror line that undoes it after. Choose and un-choose always come in pairs.

7. Edge Cases

• Empty input: The base case triggers immediately on the first call. We add an empty list to results and return. Output: [[]].

• Single element: One permutation of one element. Output: [[1]].

• Two elements: Two permutations. Good sanity check — verify both orderings appear.

• Distinct elements only: No deduplication needed. If the problem ever introduces duplicates, the used array approach adapts more cleanly than the swap approach.

8. Full Solution

import java.util.ArrayList;
import java.util.List;

public class Permutations {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used,
                                   List<Integer> path,
                                   List<List<Integer>> result) {

        if (path.size() == nums.length) {
            // copy — don't store the reference
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            used[i] = true;       // choose
            path.add(nums[i]);

            backtrack(nums, used, path, result);  // explore

            path.remove(path.size() - 1);  // un-choose
            used[i] = false;
        }
    }
}

One easy bug to watch for: when storing a completed permutation, you must copy path - new ArrayList<>(path) - rather than storing the reference directly. The same path object gets modified throughout the recursion. If you store a reference, every entry in result will end up pointing to the same (eventually empty) list.

9. Test Your Solution

System.out.println(permute(new int[]{}));
// [[]]

System.out.println(permute(new int[]{1}));
// [[1]]

System.out.println(permute(new int[]{1, 2}));
// [[1,2], [2,1]]

System.out.println(permute(new int[]{1, 2, 3}));
// 6 permutations — verify all are present and none are duplicated

System.out.println(permute(new int[]{-1, 0, 1}));
// Works with negatives — 6 permutations

For the three-element case, don't just check the count. Verify that the specific permutations make sense - trace the first two or three by hand against your mental model of the recursion tree. If the order of results matches your trace, you have strong confidence the logic is correct.

10. Key Lessons for Future Problems

• Backtracking is about managing state, not clever tricks. The algorithm is simple. The discipline is in ensuring that every modification to shared state gets undone before you try the next option. If you internalize choose → explore → un-choose, you can apply it to dozens of problems.

• The recursion tree is your map. When reasoning about backtracking problems, draw the tree. Each node is a state. Each edge is a choice. Each leaf is either a valid result or a dead end. The code is just a systematic traversal of that tree.

• Always copy before storing. Storing a reference to a mutable list is one of the most common bugs in backtracking problems. Always snapshot the current path when you record a result.

• Recognize the pattern, then adapt it. The structure here - loop through candidates, skip invalid ones, choose, recurse, un-choose - is nearly identical in Subsets, Combination Sum, and Palindrome Partitioning. Once you own it for Permutations, those problems become much more approachable.

• Factorial output means focus on clarity, not cleverness. There's no asymptotically faster solution here. What interviewers are evaluating is whether your code is clean, correct, and clearly organized. A well-structured backtracking solution with good variable names is exactly what they want to see.

Permutations teaches a core interview skill: exploring a massive search space systematically without losing control. Once that clicks, many recursive problems start feeling like variations on a familiar theme.

Good Luck and Happy Coding!