Skip to main content

21. Permutations

mediumAsked at Wise

Generate every permutation of a distinct-integer array — Wise uses this to probe controlled backtracking, which is the same pattern as enumerating FX routing legs.

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

Problem

Given an array of distinct integers, return all possible permutations of those integers. You may return the answer in any order.

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All integers are distinct

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. Generate all length-n sequences then filter

Try every length-n combination of values and keep those that are permutations.

Time
O(n^n)
Space
O(n^n)
const out=[];
function g(cur){
  if (cur.length===nums.length){
    if (new Set(cur).size===nums.length) out.push([...cur]);
    return;
  }
  for (const v of nums){ cur.push(v); g(cur); cur.pop(); }
}
g([]); return out;

Tradeoff:

2. Backtracking with used set

Track which indices are used; recurse choosing the next available value. Each branch consumes one element and restores it on return.

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

Tradeoff:

Wise-specific tips

Wise grades whether your backtracking is clean — leaked state between branches is the same bug class as a leaked balance between FX legs in their routing experiments.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →