Skip to main content

19. Permutations

mediumAsked at Grab

Return all permutations of a distinct-element array — Grab uses this as a backtracking and state-tracking check.

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

Problem

Given an array nums of distinct integers, return all possible permutations of its elements.

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All nums 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 = [1]
Output
[[1]]

Approaches

1. Insertion recursion

For each element, insert into every position of every existing partial permutation.

Time
O(n * n!)
Space
O(n * n!)
let perms = [[]];
for (const x of nums) {
  const next = [];
  for (const p of perms)
    for (let i = 0; i <= p.length; i++)
      next.push([...p.slice(0, i), x, ...p.slice(i)]);
  perms = next;
}

Tradeoff:

2. Backtracking with used set

Recurse over remaining unused indices; restore state after each branch.

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

Tradeoff:

Grab-specific tips

Grab interviewers want a clean backtracking template — frame as enumerating all delivery-stop orderings before route optimization.

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 Grab interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →