Coding problem · Medium · Backtracking

Permutations

Medium Algorithms & data structures Seen at Microsoft, Meta, LinkedIn

Given an array nums of distinct integers, return all possible permutations, in any order.

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]]

Hints

Hint 1

Build a permutation position by position, tracking which numbers are already used.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n · n!) · Space O(n)

Backtracking with a used set: at each depth, try every unused number, recurse, then undo. When the current permutation has all n numbers, record a copy. There are n! permutations, each built in O(n).

Reference solution

function permute(nums) {
  const out = [];
  const cur = [];
  const used = new Set();
  const go = () => {
    if (cur.length === nums.length) return void out.push([...cur]);
    for (const x of nums) {
      if (used.has(x)) continue;
      used.add(x); cur.push(x);
      go();
      cur.pop(); used.delete(x);
    }
  };
  go();
  return out;
}

function permute(nums: number[]): number[][] {
  if (nums.length <= 1) return [nums.slice()];
  return nums.flatMap((x, i) => permute([...nums.slice(0, i), ...nums.slice(i + 1)]).map((p) => [x, ...p]));
}

def permute(nums: list[int]) -> list[list[int]]:
    out: list[list[int]] = []
    cur: list[int] = []
    used: set[int] = set()

    def go() -> None:
        if len(cur) == len(nums):
            out.append(cur[:])
            return
        for x in nums:
            if x not in used:
                used.add(x)
                cur.append(x)
                go()
                cur.pop()
                used.remove(x)

    go()
    return out

<?php

function permute(array $nums): array
{
    if (count($nums) <= 1) {
        return [$nums];
    }
    $out = [];
    foreach ($nums as $i => $x) {
        $rest = $nums;
        unset($rest[$i]);
        foreach (permute(array_values($rest)) as $p) {
            $out[] = [$x, ...$p];
        }
    }
    return $out;
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        go(nums, new ArrayList<>(), new boolean[nums.length], out);
        return out;
    }

    private void go(int[] nums, List<Integer> cur, boolean[] used, List<List<Integer>> out) {
        if (cur.size() == nums.length) { out.add(new ArrayList<>(cur)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; cur.add(nums[i]);
            go(nums, cur, used, out);
            cur.remove(cur.size() - 1); used[i] = false;
        }
    }
}

Subsets · Medium