Skip to main content

47. Permutations

mediumAsked at Snowflake

Generate all permutations of a distinct-integer array. Snowflake asks this to test backtracking with a used-mask — relevant for join-order enumeration where the planner permutes table orderings to find the optimal plan.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake compiler-team uses this to anchor join-order enumeration discussion.
  • LeetCode Discuss (2025-11)— Recurring at Snowflake new-grad onsites.

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. Insert into every position

Recursively, take the first element, insert into every position of every recursively-generated permutation of the rest.

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

Tradeoff: Correct but allocates many intermediates. Mention as an alternative.

2. Backtracking with used-mask (optimal)

Maintain a path and a boolean used[] array. Recurse choosing any unused index; mark used; recurse; unmark on return.

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

Tradeoff: Minimal allocation per call. Same pattern as join-order enumeration in a planner.

Snowflake-specific tips

Snowflake interviewers want the used-mask version because it directly mirrors join-order enumeration. Bonus signal: discuss dynamic-programming-with-bitmask join-order optimization (Selinger-style) and how it caches subplan costs keyed on the bitmask of joined tables.

Common mistakes

  • Forgetting to unmark used[i] on return — corrupts subsequent iterations.
  • Pushing path itself instead of a copy — all results share the same mutated array.
  • Sorting the input to dedup, missing that the problem says distinct.

Follow-up questions

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

  • Permutations II (LC 47) — with duplicates.
  • Next Permutation (LC 31) — lex next.
  • Selinger join-order optimization with bitmask DP.

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 removing from input?

Mutating the input via splice is O(n) per operation and harder to undo. used[] is O(1) per check/set.

How does this connect to join ordering?

A SQL planner enumerating join orders is essentially permuting tables. Bitmask DP caches the best plan for each subset of tables, making System R's O(n!) into O(2^n * n) — still expensive, but tractable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →