43. Permutations

Build a permutation one element at a time. At each step choose any of the not-yet-used numbers, recurse, then undo the choice so the next branch can try a different number. When the path uses all numbers, it's a complete permutation.

Idea

A permutation is a specific ordering of every element. We build one incrementally: pick a first element, then a second from what's left, and so on. Backtracking explores this decision tree — after fully exploring one choice we undo it (remove it from the path) and try the next, guaranteeing we enumerate every ordering exactly once.

Algorithm

backtrack(path, remaining):

1. If remaining is empty, path is a full permutation — record a copy.
2. Otherwise, for each index i in remaining:
   • Choose: append remaining[i] to path.
   • Explore: recurse with that element removed from remaining.
   • Un-choose: pop it back off path.

Worked example: [1,2,3]

• Choose 1 → from {2,3}: [1,2,3], [1,3,2].
• Choose 2 → from {1,3}: [2,1,3], [2,3,1].
• Choose 3 → from {1,2}: [3,1,2], [3,2,1].

Result: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].

Complexity

• Time: O(n · n!) — n! permutations, each O(n) to build.
• Space: O(n) recursion depth (plus the output).

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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> remaining = new ArrayList<>();
        for (int n : nums) {
            remaining.add(n);
        }
        backtrack(new ArrayList<>(), remaining, result);
        return result;
    }

    private void backtrack(List<Integer> path, List<Integer> remaining, List<List<Integer>> result) {
        if (remaining.isEmpty()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < remaining.size(); i++) {
            path.add(remaining.get(i));
            List<Integer> next = new ArrayList<>(remaining);
            next.remove(i);
            backtrack(path, next, result);
            path.remove(path.size() - 1);
        }
    }
}