DSA Tracker

Medium

Permutations

A medium Backtracking problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.

Topic
Backtracking
Sheets
3
Core for
0 roles
Platform
LeetCode
Practice in the compilerWatch this solved step by step

The problem

Given an array of distinct integers, return all possible permutations. A permutation is an arrangement of all elements in every possible order.

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]]
Why
There are 3! = 6 permutations of three distinct elements.

Example 2

Input
nums = [0, 1]
Output
[[0,1], [1,0]]
Why
There are 2! = 2 permutations of two elements.

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All integers in nums are distinct

How to think about it

Updated 2026-09-09

Every position in the permutation must be filled by an unvisited element. Rather than tracking indices forward as in combinations, permutations require drawing from the entire pool of unused elements at every step, meaning the decision state is purely which items remain unplaced.

Approaches, worst first

  1. Path list with linear lookup

    time O(n * n!) · space O(n)

    Build a list step-by-step. In each recursive call, loop over all elements in nums and check if the current element is already present in the path list. Linear scans inside the loop add an unnecessary factor of n to each state.

  2. Boolean visited array

    time O(n * n!) · space O(n)

    Maintain a boolean array used[i] to track whether nums[i] is currently in the path. Reduces membership check to O(1). When path length equals n, snapshot the list and backtrack by unmarking used[i].

  3. In-place swappingWrite this one

    time O(n * n!) · space O(n)

    Fix elements position by position. At index first, swap nums[first] with nums[i] for every i from first to n - 1, recurse on first + 1, and swap back. Avoids extra visited structures and dynamic path lists entirely.

Where people lose marks · 3
  • Failing to revert the swap in the in-place approach. Omitting the clean-up swap corrupts the array order for subsequent iterations at the same recursion level.
  • Pushing the mutating array itself into the output list instead of a defensive clone, leaving every result matching the final unswapped state.
  • Assuming n is large: with n capped at 6, recursion depth is at most 6, so bitmasks or simple boolean arrays are well within stack limits.

The theory behind it

Backtracking — the ground this problem stands on. All Backtracking problems

What Backtracking is

Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.

When to reach for it

Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.

How the pattern works

Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.

What each operation costs

OperationTime
generate all subsets of n elementsO(2^n)
generate all permutations of n elementsO(n!)
auxiliary recursion stack memory depthO(n)
What usually goes wrong with Backtracking
  • Adding a mutable path list directly to the final answers collection without creating a shallow copy, leaving every saved result empty once backtracking finishes.
  • Forgetting to undo a state change after the recursive call returns, contaminating subsequent branches with leftover moves from earlier paths.
  • Generating duplicate subsets or permutations by failing to sort the input array and skip adjacent identical elements during branch selection.

Track this in your role's order

Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.

Start free

More Backtracking problems

Problem set and role mapping as of .