Permutations — Solution

Problem

Given a list of distinct integers, return every possible ordering of those integers. Each number must appear exactly once per arrangement, and you can return the results in any order.

Example:

• Input: nums = [1, 2, 3]
• Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• Explanation: There are 3! = 6 ways to arrange three distinct numbers.

Intuition

At each position in a permutation you can place any number that hasn't been used yet. If you think of building the arrangement slot by slot, each slot has progressively fewer choices. This cascading structure is exactly what backtracking models: try a candidate, recurse to fill the remaining slots, then undo the choice and try the next one.

Solution — Backtracking

Maintain a used boolean array so you always know which numbers are still available. At each level, iterate over every index, skip those marked used, and recurse after marking the chosen number.

Steps:

1. Initialize a used boolean array (all false) and an empty current_perm list.
2. At each recursive call, iterate over every index in nums.
3. Skip any index already marked used.
4. Mark the chosen index used and append the value to current_perm.
5. Recurse to fill the next slot.
6. When current_perm reaches the length of nums, copy it into results — this is one complete permutation.
7. After returning from recursion, remove the last element and unmark the index to backtrack.

1def permute(nums):
2    results = []
3    used = [False] * len(nums)
4
5    def backtrack(current_perm):
6        if len(current_perm) == len(nums):
7            results.append(current_perm[:])  # copy before backtracking mutates it
8            return
9        for i in range(len(nums)):
10            if used[i]:
11                continue
12            used[i] = True
13            current_perm.append(nums[i])
14            backtrack(current_perm)
15            current_perm.pop()   # undo so the next iteration starts clean
16            used[i] = False
17
18    backtrack([])
19    return results

• Time: O(n · n!) — there are n! complete permutations and copying each takes O(n)
• Space: O(n) — recursion depth reaches n and the used array is size n; result storage is O(n · n!) but not counted as auxiliary

Complexity Summary

Common Mistakes

• Not copying the permutation before saving it: Appending current_perm directly means every entry in results points to the same list, which ends up empty after backtracking finishes. Always copy (slice, new list, or equivalent).
• Forgetting to reset used[i] after returning: Omitting used[i] = false means subsequent iterations can't use numbers they're entitled to, producing incorrect or missing permutations.
• Confusing this with Permutations II (with duplicates): Because all elements here are distinct, there is no need to sort nums or skip same-value adjacent choices; adding that guard here would incorrectly prune valid arrangements.
• Appending a reference to current_perm inside the loop rather than at the base case: The snapshot must be taken when the permutation is complete, not one element at a time inside the recursion loop.

Related Problems

• subsets — same backtrack-add-recurse-undo skeleton applied to subset selection instead of full arrangements
• combination-sum-ii — backtracking with a running sum target and duplicate avoidance
• letter-combinations-of-a-phone-number — backtracking to build strings from digit-to-letter mappings
• next-permutation — find the next lexicographic arrangement in-place without generating all permutations
• palindrome-partitioning — backtracking that chooses split points rather than array elements