Subsets and Duplicates

These problems teach the most important backtracking decision:

For each candidate, should it appear in this answer?

The start index means that all choices before start have already been decided. Moving only left-to-right prevents the same subset from being generated in a different order.

Pattern summary

Problem	State	Branches	Completion	Special rule
Sum of All Subsets XOR Total	index, running XOR	include / exclude	index reaches n	accumulate instead of saving a path
Subsets	start index, path	choose any later value	every DFS state is an answer	save before branching
Subsets II	start index, path	choose any later value	every DFS state is an answer	sort; skip same-depth duplicates

1. Sum of All Subsets XOR Total

Problem

Recognition

Every element has two choices: include it in the current subset XOR or exclude it. The output is a number rather than a list, so we carry the running XOR instead of a path.

DFS contract

dfs(i, xor) adds the XOR total of every subset formed from indices i...n - 1, assuming the chosen prefix XOR is xor.

JavaScript

function subsetXORSum(nums) {
  let total = 0;
 
  function dfs(i, xor) {
    if (i === nums.length) {
      total += xor;
      return;
    }
 
    dfs(i + 1, xor);           // exclude nums[i]
    dfs(i + 1, xor ^ nums[i]); // include nums[i]
  }
 
  dfs(0, 0);
  return total;
}

Why it works

Every root-to-leaf path makes exactly one include/exclude decision per number, so it corresponds to exactly one subset. At a leaf, xor is that subset’s XOR total.

• Time: O(2^n)
• Auxiliary space: O(n) recursion stack
• Backtracking detail: no mutable path exists here, so there is nothing to undo.

2. Subsets

Problem

Recognition

Return every subset of distinct values. The empty subset is valid, and every partially built path is already a valid subset. That is why we save path at the top of each DFS call rather than only at leaves.

DFS contract

dfs(start) adds every subset that extends the current path using values from start...n - 1.

JavaScript

function subsets(nums) {
  const result = [];
  const path = [];
 
  function dfs(start) {
    result.push([...path]);
 
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }
 
  dfs(0);
  return result;
}

Why the index prevents duplicates

After choosing nums[i], the next choice can only come from i + 1 onward. A path can form [1, 2], but never later go back to form [2, 1]. Since order does not matter for a subset, that is exactly what we want.

• Time: O(n * 2^n) — there are 2^n results and copying one can take O(n).
• Auxiliary space: O(n) for the path and recursion, excluding output.

Include / exclude equivalent

The loop version above is usually easier to extend to duplicate inputs. The binary decision-tree version is equally valid:

function subsets(nums) {
  const result = [];
  const path = [];
 
  function dfs(i) {
    if (i === nums.length) {
      result.push([...path]);
      return;
    }
 
    dfs(i + 1); // exclude
 
    path.push(nums[i]);
    dfs(i + 1); // include
    path.pop();
  }
 
  dfs(0);
  return result;
}

3. Subsets II

Problem

What changes

The same index rule still prevents reordered answers. It does not prevent two equal values at the same level from producing the same subset:

• choose the first 2 as the next value,
• choose the second 2 as the next value.

Both branches describe the same result. Sort first, then allow only the first equal value to start a branch at each DFS depth.

DFS contract

dfs(start) adds every unique subset extending the current path with values from start...n - 1.

JavaScript

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
 
  const result = [];
  const path = [];
 
  function dfs(start) {
    result.push([...path]);
 
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
 
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }
 
  dfs(0);
  return result;
}

The critical line

for (let i = start; i < nums.length; i++) {
  if (i > start && nums[i] === nums[i - 1]) continue;
  // use nums[i] as the next path value
}

• i > start: another candidate has already been tried for this one position in the path.
• nums[i] === nums[i - 1]: this candidate would create an identical branch.

It is correct to choose equal values at different depths. For [1, 2, 2], choosing the first 2, then choosing the second 2 produces the valid subset [2, 2].

• Time: O(n * 2^n) worst case.
• Auxiliary space: O(n), excluding output.

Comparison: unique values vs. duplicate values

Question	Subsets	Subsets II
Sort input?	not needed	yes
Save a result at every DFS call?	yes	yes
Move forward after choosing?	dfs(i + 1)	dfs(i + 1)
Skip duplicates?	no	only when i > start

Recall prompt

Given a new “return all unique selections” problem, say:

I will sort the candidates. My DFS receives the first index I may choose. At each depth I skip equal candidates after the first one, choose a candidate, recurse from the next index, and undo the path choice.

Next: 02 - Combinations and Targets