Skip to main content

47. Permutations

mediumAsked at Reddit

Generate all permutations of distinct integers. Reddit uses this to test backtracking — the same pattern they'd use to enumerate orderings of A/B test variants for users.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common backtracking question.

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. Build with 'used' set

Track which indices are used; recurse picking any unused index.

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

Tradeoff: Classic backtracking with a boolean array.

2. Swap-in-place (optimal)

At each recursion level, swap each later element to the current position, recurse, swap back.

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

Tradeoff: No 'used' array. In-place swaps make memory access cleaner.

Reddit-specific tips

Reddit interviewers want either solution. Bonus signal: discuss when swap-in-place breaks (with duplicates — gives LC 47 territory). Mention Heap's algorithm if asked for an iterative version.

Common mistakes

  • Pushing nums directly instead of [...nums] (mutation leaks).
  • Forgetting to swap back after recursion.
  • Recursing past start === nums.length (off by one).

Follow-up questions

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

  • Permutations II (LC 47) — with duplicates.
  • Next permutation (LC 31).
  • Kth permutation sequence (LC 60).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

How many permutations of n distinct elements?

n!. 6! = 720, well within problem constraints.

Could we generate them iteratively?

Yes — Heap's algorithm, or repeatedly applying next permutation from sorted order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →