Skip to main content

46. Permutations

mediumAsked at Microsoft

Permutations is Microsoft's introduction to backtracking. Given distinct integers, generate every ordering. The standard template — pick, recurse, unpick — is what the interviewer is grading; the in-place swap variant is the bonus answer for the same complexity in less memory.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Office/Azure org onsite reports list Permutations as a recurring 30-minute backtracking medium.
  • Blind (2025-11)— Microsoft L60/L61 reports include Permutations as the backtracking warm-up before harder combinatorial questions.

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

Approaches

1. Backtracking with used[] (optimal canonical)

Maintain current[] (the partial perm) and used[] (bool per index). Recurse — when current.length === n push a copy; otherwise try each unused index, mark used, recurse, unmark.

Time
O(n * n!)
Space
O(n) recursion + O(n!) output
function permute(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);
  const current = [];
  function backtrack() {
    if (current.length === nums.length) {
      result.push(current.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(nums[i]);
      backtrack();
      current.pop();
      used[i] = false;
    }
  }
  backtrack();
  return result;
}

Tradeoff: The canonical backtracking template. The current.slice() push is essential — otherwise every output row points to the same mutable array. n! permutations each of length n gives the O(n * n!) bound.

2. In-place swap

Walk i from 0 to n-1. At each level, swap nums[i] with each nums[j] for j >= i, recurse, then swap back.

Time
O(n * n!)
Space
O(n) recursion
function permute(nums) {
  const result = [];
  function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]]; }
  function backtrack(start) {
    if (start === nums.length) {
      result.push(nums.slice());
      return;
    }
    for (let i = start; i < nums.length; i++) {
      swap(nums, start, i);
      backtrack(start + 1);
      swap(nums, start, i);
    }
  }
  backtrack(0);
  return result;
}

Tradeoff: No used[] needed — the 'fixed prefix' invariant is maintained by the start index. Same complexity, slightly tighter memory. Microsoft graders like seeing both.

Microsoft-specific tips

Microsoft is grading the backtracking template specifically — the pick / recurse / unpick three-line pattern. Say it out loud BEFORE coding: 'at each step I pick one unused number, recurse on the smaller problem, then unpick to try the next.' Trace n=2 by hand to verify the unpick — that's where most candidates accidentally leave state dirty.

Common mistakes

  • Pushing current directly instead of current.slice() — every output row aliases the same mutable array.
  • Forgetting to unpick (current.pop() and used[i] = false) — every later iteration sees stale state.
  • Trying to skip permutations involving duplicates without first sorting (only matters in LC 47 Permutations II).

Follow-up questions

An interviewer at Microsoft may pivot to one of these next:

  • Permutations II (LC 47) — input may have duplicates; sort + skip same-value siblings.
  • Combinations (LC 77) — order doesn't matter; pass start index to avoid duplicates.
  • Subsets (LC 78) — every subset, not just permutations.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What's the time complexity really?

There are n! permutations, each takes O(n) to copy into the result, so O(n * n!). Each backtrack node also does O(n) work for the loop and used[] check, but the leaf copy dominates.

When to use the swap version?

When memory matters. The swap version skips the used[] array. Same complexity in time, slightly better constants. Microsoft will accept either.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Permutations and other Microsoft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →