Leetcode 40: Combination Sum II

 

1. Problem Statement (Simple Explanation):

You are given:

• An array candidates (may contain duplicates).

• An integer target.

You must return all unique combinations of numbers from candidates such that:

• The sum of the chosen numbers equals target.

• Each number can be used at most once in each combination.

• The result must not contain duplicate combinations.

• Return combinations in any order.

2. Examples:

Example 1:

Input:

candidates = [10,1,2,7,6,1,5]

target = 8

Possible unique combinations:

• [1,1,6]

• [1,2,5]

• [1,7]

• [2,6]

Output:

[

  [1,1,6],

  [1,2,5],

  [1,7],

  [2,6]

]

Example 2:

Input:

candidates = [2,5,2,1,2]

target = 5

Valid unique combinations:

• [1,2,2]

• [5]

Output:

[

  [1,2,2],

  [5]

]

3. Key Differences vs. Combination Sum (Problem 39):

• Here, each candidate can be used at most once.

• candidates may contain duplicates, but the result must have no duplicate combinations.

• We must carefully skip duplicates at the same decision depth.

So the main changes:

• We sort candidates.

• We move forward with i + 1 when recursing (no reuse).

• We skip candidates[i] if it is the same as candidates[i-1] at the same depth.

4. Approach – Backtracking with Sorting and Duplicate Skipping:

Intuition:

Use backtracking (DFS):

• Sort candidates so duplicates are adjacent.

• At each recursive call, we iterate over indices i from start to end:

• If i > start and candidates[i] == candidates[i-1], skip this i (to avoid duplicate combinations starting with the same prefix).

• Include candidates[i] once:

• Add to current path.

• Recurse with start = i + 1 (no reuse).

• Backtrack.

We also prune when:

• remaining < 0 → stop.

• If sorted, we can break when candidates[i] > remaining (optional optimization).

Algorithm (Step-by-Step):

1. Sort candidates.

2. Define result list results.

3. Define backtrack(start, remaining, current):

• If remaining == 0:

• Add a copy of current to results.

• Return.

• For i from start to len(candidates)-1:

• If i > start and candidates[i] == candidates[i-1]:

• continue (skip duplicates at this level).

• If candidates[i] > remaining:

• break (since further ones will be even larger).

• Add candidates[i] to current.

• Call backtrack(i + 1, remaining - candidates[i], current) (note i+1, not i).

• Remove last element from current (backtrack).

4. Call backtrack(0, target, []).

5. Return results.

Pseudo-code:

Complexity:

Let:

• n = len(candidates).

Complexity is exponential in general (combinatorial):

• Time: worst-case O(2n), but constrained by small target and pruning.

• Space:

• Recursion depth up to n.

• Current combination list up to length n.

• So O(n) auxiliary space.

Constraints (target ≤ 30, candidates[i] ≤ 50) keep it practical.

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code: