66. Permutations

Given an array nums of distinct integers, return every possible ordering (permutation) of its elements.

Each permutation must appear exactly once; the list of permutations may be returned 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 = [0,1]
Output: [[0,1],[1,0]]

Example 3

Input: nums = [1]
Output: [[1]]

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All values in nums are distinct

Follow-up: How would you avoid duplicate permutations if nums could contain repeated values?

💡 Hint 1

There are n! permutations. Build them one position at a time.

💡 Hint 2

Backtracking: keep the current partial permutation and a used flag per element. At each step, try every unused element, recurse, then undo the choice.

💡 Hint 3

When the partial permutation has length n, add a copy of it to the answer.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Backtracking. Maintain path (the permutation built so far) and a used array. At each depth, loop over all elements; for every one not yet used, mark it, append it, recurse, then pop it and unmark it. When path holds all n elements, record a copy. Every permutation is produced exactly once because each level fixes one more position with a different unused element.

Time O(n · n!)Space O(n) besides the output

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  const build = () => {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      build();
      path.pop();
      used[i] = false;
    }
  };
  build();
  return result;
}

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

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

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit