Combinations and Targets

Combination problems choose values in increasing index order, so [2, 3] and [3, 2] are never both generated. The key question is what happens to the index after a value is chosen:

• stay on the same index when a value may be reused;
• move to the next index when each input occurrence may be used once.

Pattern summary

Problem	DFS state	After choosing candidate i	Duplicate handling
Combination Sum	start, remaining	recurse with i	candidates are distinct
Combination Sum II	start, remaining	recurse with i + 1	sort and skip same-depth duplicates
Combinations	start, path	recurse with value + 1	natural increasing range

4. Combination Sum

Problem

Recognition

Return combinations that add to a target. Each candidate is positive and may be used any number of times. A remaining target makes both the goal and failure condition direct.

DFS contract

dfs(start, remaining) finds every combination extending path that sums to remaining, using candidates at indices start... and allowing reuse.

JavaScript

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
 
  const result = [];
  const path = [];
 
  function dfs(start, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
 
    for (let i = start; i < candidates.length; i++) {
      const candidate = candidates[i];
      if (candidate > remaining) break;
 
      path.push(candidate);
      dfs(i, remaining - candidate); // i: candidate may be reused
      path.pop();
    }
  }
 
  dfs(0, target);
  return result;
}

Why no duplicate combinations appear

The path is non-decreasing because the next recursive call starts at i, never before it. [2, 2, 3] can be formed, but [3, 2, 2] cannot.

Complexity

Let h = target / min(candidates) be the maximum path length. The search is exponential in h; copying answers adds their length. Auxiliary recursion/path space is O(h).

5. Combination Sum II

Problem

What changes

Each input occurrence can be chosen once, and equal values may be present. This changes two lines:

1. recurse with i + 1, not i;
2. skip duplicate choices at the same depth.

DFS contract

dfs(start, remaining) finds every unique combination extending path that sums to remaining, using each candidate occurrence at most once.

JavaScript

function combinationSum2(candidates, target) {
  candidates.sort((a, b) => a - b);
 
  const result = [];
  const path = [];
 
  function dfs(start, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
 
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
 
      const candidate = candidates[i];
      if (candidate > remaining) break;
 
      path.push(candidate);
      dfs(i + 1, remaining - candidate); // i + 1: use this occurrence once
      path.pop();
    }
  }
 
  dfs(0, target);
  return result;
}

Why the duplicate guard is placed before the target pruning

Both checks are safe after sorting. The duplicate guard expresses uniqueness; the break expresses impossibility for this candidate and every later, larger candidate. Keeping them beside each other makes the two reasons for sorting visible.

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

6. Combinations

Problem

Recognition

Choose k values from [1, 2, ..., n]. It is a subset problem with a fixed answer length. The path must be increasing, so start is again the key state.

DFS contract

dfs(start) appends every length-k combination that extends path using values from start...n.

JavaScript

function combine(n, k) {
  const result = [];
  const path = [];
 
  function dfs(start) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }
 
    const stillNeeded = k - path.length;
    for (let value = start; value <= n - stillNeeded + 1; value++) {
      path.push(value);
      dfs(value + 1);
      path.pop();
    }
  }
 
  dfs(1);
  return result;
}

The small but useful prune

If stillNeeded values remain, the current choice cannot exceed n - stillNeeded + 1. Choosing a larger value would leave too few values to fill the path.

• Time: O(k * C(n, k)) including result copies.
• Auxiliary space: O(k), excluding output.

Reuse / once / fixed-size comparison

Problem	What makes one branch?	Next start	Completion
Combination Sum	choose a candidate that fits	i	remaining is zero
Combination Sum II	choose an unused candidate occurrence	i + 1	remaining is zero
Combinations	choose the next increasing number	value + 1	path length is k

Recall prompt

I will sort when target pruning or duplicates matter. The DFS receives the first legal candidate index and the remaining target. Reuse means recurse with the same index; one-time use means recurse with the next index. For duplicate input, I skip equal candidates only at the same depth.

Next: 03 - Permutations