Skip to main content

45. Permutations

mediumAsked at Workday

Generate all permutations of an array of distinct integers. Workday uses this as the canonical backtracking baseline — same shape as enumerating role-rotation schedules.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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. Iterative insertion

Start with [[]]. For each num, insert into every position of every existing perm.

Time
O(n * n!)
Space
O(n * n!)
// build up by inserting nums[i] into each slot of each existing perm — O(n!) work

Tradeoff: Works but harder to extend (e.g., with constraints).

2. Backtracking with used set

Build path. At each level, try every unused element.

Time
O(n * n!)
Space
O(n) stack)
function permute(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);
  function backtrack(current) {
    if (current.length === nums.length) { result.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 result;
}

Tradeoff: Standard backtracking template. Used array tracks which elements are already in path.

Workday-specific tips

Workday grades the backtracking template: in/out invariant (used[i] = true before recurse, false after). Push a COPY of current — pushing the reference results in everyone sharing the same mutating array.

Common mistakes

  • Pushing current directly without copying — all results end up as the same array.
  • Forgetting to undo used[i] = true after the recursive call.
  • Returning n! arrays sharing pointers.

Follow-up questions

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

  • Permutations II (LC 47) — handles duplicate inputs.
  • Next Permutation (LC 31).
  • 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

Why a used array?

We need to know which elements are already in the partial permutation. A set works too; an array is faster for small n.

Why backtracking and not swapping?

Swapping is fine and a popular variant. Backtracking with used is clearer to read and extends naturally to constraints.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →