45. Permutations

Q: Why used array instead of in-place swap?

Used array is more readable. In-place swap is faster but harder to reason about — Plaid prefers the readable version for an interview.

Q: Why slice the path before pushing?

Otherwise every permutation in out points to the same array, which gets mutated by subsequent backtracking.

mediumAsked at Plaid

Return all possible permutations of distinct integers. Plaid asks this as a backtracking warm-up before harder ordering problems on transaction-processing schedules.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

LeetCode Discuss (2026)— Plaid SWE II OA.
Glassdoor (2025)— Plaid intro backtracking.

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

Approaches

1. Iterative insertion

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

Time: O(n!)
Space: O(n!)

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

Tradeoff: Allocates many intermediate arrays. Clean but not the most efficient.

2. Backtracking with used set

DFS; track which indices are used. At each step, try every unused index.

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

function permute(nums) {
  const out = [];
  const used = new Array(nums.length).fill(false);
  const path = [];
  function bt() {
    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]);
      bt();
      path.pop();
      used[i] = false;
    }
  }
  bt();
  return out;
}

Tradeoff: Standard backtracking template. The used array is the simplest way to track which elements are in the current path.

Plaid-specific tips

Plaid uses this to verify your backtracking discipline — pushing before recursion, popping after, resetting used flag. Bonus signal: discuss the in-place swap variant that avoids the used array (LC 47 style) for memory-tight production code.

Common mistakes

Forgetting to set used[i] = false after backtracking — corrupts later branches.
Pushing path directly instead of [...path] — every output ends up pointing to the same array.
Off-by-one on the base case length check.

Follow-up questions

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

Permutations II (LC 47) — with duplicates.
Next permutation (LC 31).
Permutation sequence (LC 60) — kth permutation directly.

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 array instead of in-place swap?

Used array is more readable. In-place swap is faster but harder to reason about — Plaid prefers the readable version for an interview.

Why slice the path before pushing?

Otherwise every permutation in out points to the same array, which gets mutated by subsequent backtracking.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →