Combination Sum II - Complete Backtracking Guide

Introduction

Combination Sum II is a classic backtracking problem that builds upon the foundation of Combination Sum I. The primary challenge lies in two specific constraints:

1. No Reuse of Elements: Each number in the candidates array may only be used once in a combination.
2. Unique Combinations: The solution set must not contain duplicate combinations.

This guide will walk you through the logic, algorithm, and implementation of solving this problem efficiently using backtracking.

Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Constraints:

• The same number may be chosen from candidates an unlimited number of times.
• Note: The solution set must not contain duplicate combinations.
• Each number in candidates may only be used once in the combination.

Key Differences from Combination Sum I

| Feature | Combination Sum I | Combination Sum II |

| :--- | :--- | :--- |

| Element Usage | Unlimited times | At most once |

| Duplicates | Allowed in input | Allowed in input, but output must be unique |

| Sorting Requirement | Optional | Mandatory for optimization |

The Backtracking Strategy

Backtracking is a depth-first search (DFS) approach where we explore all possible paths (combinations) recursively. If a path leads to a solution, we keep it. If it exceeds the target or leads to a dead end, we backtrack (undo the last choice).

The Critical Sorting Step

Before starting the recursion, we must sort the candidates array. This allows us to:

1. Prune branches early (if the current number exceeds the remaining target, we can stop the loop).
2. Implement the logic to skip duplicate numbers efficiently.

The Duplicate Skipping Logic

The most common point of confusion is how to skip duplicates without losing valid combinations.

The Rule: If candidates[i] == candidates[i-1], we skip candidates[i] only if i > startIndex.

• i > startIndex: This ensures we don't skip the first occurrence of a number in the current recursive level. If we skip the first one, we might miss a valid combination starting with that number.
• i > 0: This ensures we don't compare the first element with a non-existent previous element.

Algorithm Steps

1. Sort the input array.
2. Define a recursive function backtrack(startIndex, path, remainingSum):

• Base Case: If remainingSum === 0, add the current path to the result.
• Pruning: If remainingSum < 0, return immediately (no need to proceed).

1. Iterate from startIndex to the end of the array:

• Check Target: If candidates[i] > remainingSum, break (since array is sorted, subsequent numbers will be larger).
• Skip Duplicates: If i > startIndex && candidates[i] === candidates[i-1], continue.
• Action: Add candidates[i] to path and call backtrack(i + 1, path, remainingSum - candidates[i]).
• Backtrack: Remove the last element from path (pop) to explore other possibilities.

Code Implementation (TypeScript)

function combinationSum2(candidates: number[], target: number): number[][] {
  const result: number[][] = [];
  // Sort to handle duplicates and enable pruning
  candidates.sort((a, b) => a - b);

  const backtrack = (
    startIndex: number,
    path: number[],
    remainingSum: number
  ) => {
    // Base Case: Found a valid combination
    if (remainingSum === 0) {
      result.push([...path]);
      return;
    }

    for (let i = startIndex; i < candidates.length; i++) {
      // Pruning: If current number exceeds remaining sum, stop
      if (candidates[i] > remainingSum) {
        break;
      }

      // Skip duplicates: Only skip if it's not the first element in this level
      // and it's the same as the previous element
      if (i > startIndex && candidates[i] === candidates[i - 1]) {
        continue;
      }

      // Include candidates[i]
      path.push(candidates[i]);

      // Recurse: Move to next index (i + 1) because we can't reuse current element
      backtrack(i + 1, path, remainingSum - candidates[i]);

      // Backtrack: Remove the last element to try the next candidate
      path.pop();
    }
  };

  backtrack(0, [], target);
  return result;
}

// Example Usage
const candidates = [10, 1, 2, 7, 6, 1, 5];
const target = 8;
console.log(combinationSum2(candidates, target));
// Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

Complexity Analysis

Time Complexity: $O(2^N)$

In the worst case, we have to explore all subsets of the array. Since we are pruning branches where candidates[i] > remainingSum, the actual runtime is often better than this, but it remains exponential in the size of the input.

Space Complexity: $O(N)$

• Recursion Stack: The depth of the recursion tree is at most the length of the array, $O(N)$.
• Result Storage: The space required to store the output is not counted towards space complexity in standard Big O notation, but it is $O(K imes N)$ where $K$ is the number of valid combinations.

Common Pitfalls

1. Forgetting to Sort: Without sorting, the duplicate skipping logic fails, and you will generate duplicate combinations.
2. Incorrect Duplicate Check: Using i > 0 instead of i > startIndex will cause you to skip valid combinations. For example, if the array is [1, 1, 2], skipping the second 1 at the root level (i=0) is fine, but skipping the second 1 at the next level (i=1) would be wrong if the first 1 wasn't chosen.
3. Modifying the Input Array: Never modify the input array directly inside the function unless you restore it, as it affects the caller's data.
4. Infinite Loops: Ensure you pass i + 1 to the recursive call, not i, to ensure each element is used at most once.

Real-World Applications

• Resource Allocation: Distributing a fixed budget across different projects where each project can be selected at most once.
• Scheduling: Finding all possible time slots that fit a specific duration constraint without reusing the same resource slot.
• Inventory Management: Selecting a subset of items to reach a specific total weight or value without reusing the same inventory item.

Summary

Combination Sum II is a robust exercise in mastering backtracking nuances. The two most important takeaways are:

1. Sorting the array first to enable pruning and duplicate handling.
2. Correctly identifying when to skip duplicates using the i > startIndex condition.

By following the structure above, you can systematically break down the problem and ensure your solution is both correct and efficient.