Coding interview problems › Backtracking

🧩 Backtracking Medium

Permutations

Permutations explained: generate all n! orderings with backtracking and a used[] array, tested Python, the classic copy and undo bugs, and a live visual.

Also searched as: all permutations of an array backtracking · generate permutations recursion · print all permutations

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

Switch the lab to permutations and watch the recursion tree grow to n! leaves, one choose, explore, un-choose step at a time.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given a list of distinct integers, return every possible ordering of all of them. Any order of the output is fine.

Input[1, 2, 3]
Output[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

3! = 6

Input[1]
Output[[1]]

The key insight

Fill the positions one at a time. For the next position you may place any number not yet used. Mark it used, recurse to fill the rest, then unmark it so the next branch can use it. When the path has all n numbers, it is one complete permutation.

Brute force first: Generating all nn sequences and filtering out those with repeats wastes almost all the work.

Step-by-step approach

  1. Keep path, a boolean array used, and the output list.
  2. If len(path) == n, store a copy and return.
  3. Otherwise, for each index i not yet used: mark it, append nums[i], recurse.
  4. After the call returns, pop it and unmark it (un-choose).
  5. Return the output after dfs() finishes.

Python solution

PYTHON 3tested
def permute(nums):
    out, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True             # choose
            path.append(x)
            dfs()                      # explore
            path.pop()                 # un-choose
            used[i] = False

    dfs()
    return out

Complexity

TimeO(n · n!)
SpaceO(n)

There are n! permutations and each one costs O(n) to copy. The recursion depth, path and used are O(n) apart from the output.

Common mistakes

Frequently asked questions

What is the time and space complexity of generating permutations?

O(n × n!) time, since there are n! permutations of length n. Extra space is O(n) for recursion, path and the used array, plus the output.

How do I avoid duplicate permutations when the input has repeats?

Sort the input. While looping, skip nums[i] if it equals nums[i - 1] and used[i - 1] is False; this forces equal values to be placed in a fixed order.

Can I generate permutations by swapping?

Yes. For position k, swap each element from k onward into position k, recurse on k + 1, then swap back. It avoids the used array and works in place.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.