Permutations

MediumArray Backtracking Recursion

A relay coach wants to try out every possible running order for the team before race day. Each runner is identified by a distinct integer bib number in nums.

Return all permutations of nums: every ordering of all the runners, each listed exactly once. The orderings can be returned in any order.

Example 1

Input: nums = [4,7,2]
Output: [[4,7,2],[4,2,7],[7,4,2],[7,2,4],[2,4,7],[2,7,4]]

Explanation: Three runners can line up in 3! = 6 different orders.

Example 2

Input: nums = [-3,5]
Output: [[-3,5],[5,-3]]

Explanation: Either runner can go first.

Constraints

nums holds between 1 and 6 bib numbers.
The bib numbers are distinct integers from -10 to 10.

Follow-up: If two runners could share a bib number, how would you avoid listing the same order twice?

💡 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