Skip to main content

46. Permutations

medium

Generate every permutation of a list of distinct integers. Canonical backtracking problem with a used[] flag — every coding-interview prep list opens with this one.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

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]]

Example 2

Input
nums = [0,1]
Output
[[0,1],[1,0]]

Example 3

Input
nums = [1]
Output
[[1]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recursion tree has n! leaves. Each leaf is a permutation.

Hint 2

Track which indices are already used with a boolean array — at each depth, iterate all indices that aren't used and add them to the path.

Hint 3

When path.length == nums.length, snapshot it to the result.

Hint 4

Alternative: swap nums[i] with nums[start] in place, recurse on start+1, swap back. Saves the used[] but mutates the input.

Solution approach

Reveal approach

Two clean patterns: (1) backtrack with a path array and a used boolean array — at each depth, loop i over nums.indices, skip when used[i], otherwise push nums[i] onto path, set used[i] = true, recurse, pop and reset. When path.length == nums.length snapshot to result. (2) Swap-in-place — at depth start, for i in [start, n) swap nums[i] with nums[start], recurse with start + 1, swap back. Both run in O(n * n!) time (n! permutations, O(n) per copy); space is O(n) recursion stack.

Complexity

Time
O(n * n!)
Space
O(n)

Related patterns

  • backtracking
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Permutations and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →