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 Sam K., 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.

More Microsoft coding interview questions

See all Microsoft problems →

Companies that also ask Permutations