Permutations

MEDIUM✓ CHIP-TIMEDLC #46 — FULL STATEMENT ↗

The drill: Every possible ordering of a list of distinct numbers, using every number exactly once — return them all.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of distinct numbers arrives, and the task is to produce every possible ordering of it, using each number exactly once per ordering.

Order is the entire point: [1, 2] and [2, 1] are two different results here, unlike a subset or combination problem where only membership matters.

Every returned ordering must use all of the input numbers — none left out, none repeated within a single ordering — and every distinct ordering should appear exactly once.

EX 01

nums = [1]

→ [[1]]

MINIMUM SIZE

EX 02

nums = [1, 2]

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

EX 03

nums = [1, 2, 3]

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

CLASSIC N = 3

all input numbers are distinct
arrays stay short, since the output size is n factorial
each ordering uses every element exactly once
output order between the orderings themselves is free

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Order is the whole point here — [1, 2] and [2, 1] both count, so 'used before' isn't enough; you need 'used before, in this exact spot'.

HINT 2 THE STRUCTURE

At each position in the output, any number not yet placed is a legal next choice — build the ordering one slot at a time and undo the choice before trying the next.

HINT 3 ONE STEP FROM THE ANSWER

Swap the chosen value into the current position and recurse on the rest of the array, then swap back on the way out. The used/unused split becomes a plain array boundary — no scanning required.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SWAP-INTO-PLACE RUNPATTERN · SWAP INTO PLACEnums = [1, 2, 3]

STEP 1

Three numbers, six orderings. Swap the chosen value into the current position, recurse on the rest, then swap back — no membership scan needed.

STEP 1 / 12 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/permutations.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        def backtrack(i):
            if i == n:
                res.append(list(nums))
                return
            for j in range(i, n):
                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i + 1)
                nums[i], nums[j] = nums[j], nums[i]  # swap back

        backtrack(0)
        return res

TIME O(N·N!)SPACE O(N)PYTHON · RACE PACE · 16 LN

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        path = []

        def backtrack():
            if len(path) == n:
                res.append(list(path))
                return
            for x in nums:
                if x not in path:      # re-scan the whole array to find who's free
                    path.append(x)
                    backtrack()
                    path.pop()

        backtrack()
        return res

TIME O(N²·N!)SPACE O(N)PYTHON · TRAINING PACE · 18 LN

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, res);
        return res;
    }

    private void backtrack(int[] nums, int i, List<List<Integer>> res) {
        if (i == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int v : nums) {
                perm.add(v);
            }
            res.add(perm);
            return;
        }
        for (int j = i; j < nums.length; j++) {
            swap(nums, i, j);
            backtrack(nums, i + 1, res);
            swap(nums, i, j);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

TIME O(N·N!)SPACE O(N)JAVA · RACE PACE · 29 LN

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int x : nums) {
            if (!path.contains(x)) {
                path.add(x);
                backtrack(nums, path, res);
                path.remove(path.size() - 1);
            }
        }
    }
}

TIME O(N²·N!)SPACE O(N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED