Skip to main content

45. Permutations

mediumAsked at Datadog

Generate all permutations of a distinct-integer array. Datadog uses this as a baseline backtracking question — and follows up by asking how to lazily yield permutations as an iterator over a streaming consumer.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite 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 value, insert into every position of every existing permutation.

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

Tradeoff: Works but allocates a lot. Datadog usually wants the canonical backtracking form.

2. Backtracking with used set (optimal)

Recurse; at each level, try every unused number; mark used, recurse, unmark.

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

Tradeoff: Canonical backtracking. The used-array tracks which values are already in the prefix; same template for harder backtracking variants.

Datadog-specific tips

Datadog will follow up with: 'Now make this lazy — yield one at a time instead of materializing all of them.' Show that backtracking already IS a yielding generator if you use ES2025 generators (function*). The Output size is n! so streaming is the only practical mode for n > 8.

Common mistakes

  • Forgetting to pop AND unmark — corrupts state across branches.
  • Using a Set instead of a boolean array — slower constant factor.
  • Pushing path without copy — out gets shared references and ends up wrong.

Follow-up questions

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

  • Permutations II (LC 47) — with duplicates; skip equal siblings.
  • Next Permutation (LC 31) — generate one at a time, in lex order.
  • Permutation Sequence (LC 60) — find the kth without enumeration.

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 not swap-in-place?

The swap-in-place variant is elegant but harder to reason about. The used-array form is the canonical template that generalizes to combination-style backtracking.

Can this be a generator?

Yes — replace push to out with yield. Then iterate with for-of. Streaming-friendly: O(1) memory plus the current path.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →