Combination Sum II

Explain the Problem

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. Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example:

Input: candidates = [10,1,2,7,6,1,5], target = 8

Output:

[
  [1,1,6],
  [1,2,5],
  [1,7],
  [2,6]
]

---

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

1. Sort the Candidates: First, sort the candidates to make it easier to handle duplicates.

2. Recursive Function: We'll create a helper function that tries to build combinations by choosing each candidate only once.

3. Backtracking: If the current combination's sum equals the target, we add it to the result list. If it exceeds the target, we backtrack.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function combinationSum2(candidates, target) {
  const result = [];
  candidates.sort((a, b) => a - b); // Sort the candidates to handle duplicates easily

  // Helper function for backtracking
  function backtrack(start, path, remaining) {
    // If the remaining sum is 0, add the current path to the result
    if (remaining === 0) {
      result.push([...path]);
      return;
    }

    // Loop through the candidates starting from the current index
    for (let i = start; i < candidates.length; i++) {
      // Skip duplicates
      if (i > start && candidates[i] === candidates[i - 1]) continue;

      // If the candidate exceeds the remaining sum, break the loop
      if (candidates[i] > remaining) break;

      // Add the candidate to the path
      path.push(candidates[i]);
      // Recurse with the updated path and remaining sum
      backtrack(i + 1, path, remaining - candidates[i]);
      // Backtrack: remove the last candidate from the path
      path.pop();
    }
  }

  // Start the backtracking with an empty path and the initial target
  backtrack(0, [], target);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have a list of numbers (candidates) and you want to find all unique ways to sum up to a given number (target) using each number only once.

• Sort the Candidates: This helps us to easily skip duplicates and stop early when a candidate exceeds the target.

• Recursive Function: This is like a helper that tries to build different combinations by adding candidates to the current combination.

• Backtracking: This means if the current combination's sum exceeds the target, you go back and try a different candidate.

For each candidate, you either add it to your current combination or skip it. If you find a combination that adds up to the target, you save it. If the current sum exceeds the target, you stop and backtrack to try another candidate.

Code Explanation in Pointers

1. Sort Candidates: Sort the candidates array to handle duplicates easily.

2. Initialize Result Array: Create an empty array to store all unique combinations.

3. Define Backtracking Function: Create a recursive function to explore different combinations.

4. Base Case - Target Met: If the remaining sum is 0, add the current combination to the result.

5. Skip Duplicates: Skip duplicate candidates to avoid repeating the same combination.

6. Check Sum: If the candidate exceeds the remaining sum, break the loop.

7. Add to Path: Add the current candidate to the combination.

8. Recursive Call: Call the function recursively with the updated combination and remaining sum.

9. Backtrack: Remove the last candidate from the combination before trying the next one.

10. Start Search: Start the search with an empty combination and the initial target.

Complexity Analysis

• Time Complexity: O(2^N), where N is the number of candidates. This is because we explore each combination.

• Space Complexity: O(N), due to the recursion stack and the path array.

---