Skip to main content

45. Permutations

mediumAsked at Vercel

Generate all permutations of a distinct-integer array. Vercel asks this as the canonical backtracking question — same recursive shape as enumerating valid edge-routing orderings for their A/B traffic-split experiments.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; backtracking with used-set expected.
  • LeetCode Discuss (2026-Q1)— Listed in Vercel screen pool.

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 = [1]
Output
[[1]]

Approaches

1. Iterative insertion

Start with [[]]. For each new element, insert it into every position of every existing permutation.

Time
O(n!)
Space
O(n!)
function permute(nums) {
  let result = [[]];
  for (const n of nums) {
    const next = [];
    for (const p of result) {
      for (let i = 0; i <= p.length; i++) {
        next.push([...p.slice(0, i), n, ...p.slice(i)]);
      }
    }
    result = next;
  }
  return result;
}

Tradeoff: Works but allocates intermediate arrays at every step. Backtracking is cleaner.

2. Backtracking with used set (optimal)

DFS over positions, picking any unused element at each position. Mark/unmark via a boolean array.

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

Tradeoff: The used[] array prevents re-picking. The path array is mutated in place and copied only at leaf emission, avoiding intermediate allocations.

Vercel-specific tips

Vercel grades the backtracking version. Bonus signal: explaining the mark/unmark pattern (touch used[i] = true before recursion, false after) and the O(n * n!) complexity (n! permutations, each O(n) to copy on emit). For LC 47 (with duplicates), the same shape extends with sort + skip-equal-and-prev-unused.

Common mistakes

  • Forgetting to unmark used[i] after recursion — corrupts later iterations.
  • Forgetting to spread `[...path]` on emit — pushes a reference that gets mutated.
  • Confusing position-based vs element-based recursion — use either consistently.

Follow-up questions

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

  • Permutations II (LC 47) — duplicates allowed; dedup with sort + skip.
  • Next permutation (LC 31) — one-step navigation in the lex order.
  • Permutation Sequence (LC 60) — direct construction by factorial.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why used[] instead of indexOf?

used[] is O(1); indexOf in the path is O(n). At n! recursive calls, the difference matters.

Can I do this in O(n!) space (output dominant)?

Yes — the output IS n! * n entries. The recursive stack is O(n) and path is O(n); the dominant cost is the output collection.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →