Permutations

Permutations differ from combinations in one decisive way:

Order matters, so every unused value is a possible next choice.

There is no advancing start index. At each level, scan the full set of choices and skip the values already used in the current ordering.

Pattern summary

Problem	Track availability with	Completion	Duplicate strategy
Permutations	boolean array	path has length n	input is distinct
Permutations II	frequency map	path has length n	choose each distinct value once per level

7. Permutations

Problem

Recognition

Every ordering of distinct numbers is required. The first position can use any number; the second can use any remaining number; and so on.

DFS contract

dfs() adds every ordering that extends the current path; used[i] says whether nums[i] already appears in that path.

JavaScript

function permute(nums) {
  const result = [];
  const path = [];
  const used = Array(nums.length).fill(false);
 
  function dfs() {
    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]);
 
      dfs();
 
      path.pop();
      used[i] = false;
    }
  }
 
  dfs();
  return result;
}

Why a used array instead of a start index?

A start index says “future choices must be to my right,” which intentionally removes reordered duplicates. That would be wrong here: after choosing 2 first, the next choice must still be able to choose 1.

• Time: O(n * n!) — there are n! arrangements and each result copy costs O(n).
• Auxiliary space: O(n) for path, used, and recursion, excluding output.

8. Permutations II

Problem

What changes

If nums = [1, 1, 2], choosing the first 1 or the second 1 at the first position creates identical work. Represent choices by value frequency instead of input index:

• choose value 1 once as a branch,
• reduce its count,
• restore it after recursion.

DFS contract

dfs() adds every unique ordering that extends path; count records how many copies of each value remain.

JavaScript

function permuteUnique(nums) {
  const count = new Map();
  for (const num of nums) {
    count.set(num, (count.get(num) ?? 0) + 1);
  }
 
  const result = [];
  const path = [];
 
  function dfs() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
 
    for (const [num, frequency] of count) {
      if (frequency === 0) continue;
 
      count.set(num, frequency - 1);
      path.push(num);
 
      dfs();
 
      path.pop();
      count.set(num, frequency);
    }
  }
 
  dfs();
  return result;
}

Why the map removes duplicates

The loop visits each distinct number once. It never distinguishes between identical copies, so identical choices cannot produce separate branches. Restoring the frequency after each call preserves the state for siblings.

• Time: O(n * n!) worst case when all values are distinct; fewer unique outputs with duplicates.
• Auxiliary space: O(n), excluding output.

Another valid duplicate strategy

Sorting plus a used array also works:

nums.sort((a, b) => a - b);
 
for (let i = 0; i < nums.length; i++) {
  if (used[i]) continue;
  if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
 
  used[i] = true;
  path.push(nums[i]);
  dfs();
  path.pop();
  used[i] = false;
}

The guard says: when equal values are both currently unused, only the leftmost one may begin this position. The frequency-map solution is usually easier to reason about because it models the real choice directly: choose a value with remaining supply.

Combination vs. permutation

Question	Combination	Permutation
Does order matter?	no	yes
Can the next choice come from before the last one?	no	yes, if unused
Main state	start index	used flags or counts
Example	[1, 2] only	[1, 2] and [2, 1]

Recall prompt

Because order matters, every unused value can fill the next slot. I will scan all values at every DFS level, mark a selected value as used, recurse, then unmark it. If values repeat, I will use frequencies or skip same-level duplicate choices.

Next: 04 - Strings and Grids