Skip to main content
DSA patterns

Permutations

mediumRecursion Must-doAmazonMetaGoogle

Problem statement

You're given an array of distinct integers, nums. Return every possible ordering (permutation) of nums, in any order.

Think of it as every possible order to run a handful of independent setup scripts or config changes, when you need to check whether the order actually matters.

Examples

Example 1

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: Three distinct values have 3! = 6 possible orderings, and all six are listed.

Example 2

Input: nums = [0,1]

Output: [[0,1],[1,0]]

Explanation: Two values have 2! = 2 possible orderings.

Example 3

Input: nums = [1]

Output: [[1]]

Explanation: A single value has exactly 1! = 1 possible ordering — itself.

Hints

Hint 1: Build a permutation one position at a time: at each position, you can place any value that hasn't been placed yet.

Approach

Optimal: In-place swapping

Intuition

Instead of tracking which values have been used with a separate array, permute nums in place. At recursion depth start, everything before start is already fixed in its final position, and everything from start onward is exactly "what's still available." Try placing each remaining candidate into position start by swapping it there, recurse to fix the next position, then swap back to undo that choice before trying the next candidate. Once start reaches the end of the array, every position is fixed — record a copy of nums as one completed permutation.

Steps

  1. Define a recursive helper taking a start index.
  2. Base case: if start equals n, append a copy of nums to the result and return.
  3. Recursive case: for each index i from start to n - 1: swap nums[start] and nums[i], recurse with start + 1, then swap them back before trying the next i.
  4. Call the helper with start = 0, then return the result.

Dry run

nums = [1, 2, 3] — tracing the i = 0 and i = 1 branches at the deepest levels fully; the i = 1 and i = 2 branches at start = 0 follow the identical swap → recurse → swap-back pattern to produce the remaining four permutations:

start i swap array after action
0 0 (0,0), no-op [1,2,3] recurse to start=1
1 1 (1,1), no-op [1,2,3] recurse to start=2
2 2 (2,2), no-op [1,2,3] start=3 (end) → record [1,2,3]
1 2 (1,2) [1,3,2] start=2 (end) → record [1,3,2], then swap back to [1,2,3]

After both branches under start=1 finish, the array is restored to [1,2,3], and start=0 moves on to i=1 (swap (0,1) → [2,1,3]) and i=2 (swap (0,2) → [3,2,1]), each producing two more permutations the same way. All 6 permutations from Example 1 are produced exactly once, though not necessarily in that example's exact order.

Edge cases: nums with one element hits the base case almost immediately (start = 0, i = 0 swaps with itself, then start = 1 = n), matching Example 3.

Complexity

Time O(n! · n) - the same bound as the other two approaches; there's no way to avoid producing n! permutations, each costing O(n) to copy into the result.

Space O(1) - extra beyond the recursion stack and the output — no `used` array and no per-step list of partial permutations are needed at all, since `nums` itself is reused and restored via swaps.

from typing import List


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

        def backtrack(start: int) -> None:
            if start == len(nums):
                result.append(nums[:])
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # swap back

        backtrack(0)
        return result


if __name__ == "__main__":
    print(Solution().permute([1, 2, 3]))  # 6 permutations, order may vary
    print(Solution().permute([0, 1]))     # order may vary
    print(Solution().permute([1]))        # [[1]]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "generate every possible ordering of a small set" — permutations, n! growth
  • Idea: fix one position at a time and try every not-yet-used candidate there, either with a used array or in place via swapping; or build permutations of longer prefixes by inserting the next element into every gap of every shorter permutation
  • Cost: O(n! · n) time and space for every approach — n! permutations, each up to length n
  • Trap: forgetting to swap back (or unmark used) before trying the next candidate corrupts every later branch — the same backtracking discipline as Subsets, just with a used-tracking or swap-restore step instead of an include/exclude toggle

Interview follow-ups

  • What if nums could contain duplicates, and the result shouldn't contain duplicate permutations (Permutations II)?

    Sort nums first. In the used-array backtracking approach, skip trying a candidate at a given recursion depth if it equals the previous candidate at that same depth and the previous one hasn't been used yet on the current path (a used[i-1] == false guard). This avoids generating the same permutation twice while still correctly using every duplicate value the right number of times.

  • How would you produce just the kth permutation in lexicographic order, without generating all of them first?

    There's a direct construction based on factorials: since there are (n-1)! permutations starting with any fixed first element, the first element can be picked directly by dividing k by (n-1)!, and the same idea then repeats on the remaining n-1 elements. This answers "what's the kth permutation" in O(n²) time without ever generating the other n! - 1 permutations.

Frequently asked questions

Because the swap-based approach re-purposes nums itself as the bookkeeping: everything before start is already fixed in place, and everything from start onward is exactly "what's still available" to place next. There's no need for a separate structure to track which values have been used, since the array's own layout already encodes it.

No. Every swap made going deeper into the recursion is undone by an identical swap coming back out (the "swap back" line), so by the time the outermost call returns, nums is back in its original order. It's only ever mutated temporarily, during the recursion itself.

Because there are n! permutations total, and writing out each one costs up to O(n). Producing the full answer requires at least that much work no matter the method — whether that work is spent copying a path, inserting into every gap, or copying the array after a sequence of swaps.

Trying every possible ordering of a small set of steps — the order to run n independent setup scripts, the order to apply n config changes when order might matter, the order to check n conditions — is exactly enumerating permutations. It's only realistic to brute-force while n stays small, which is why this problem caps nums at 6 elements: 6! is 720, while 10! is already over 3.6 million.