Hide sidebar
leetcode/DSA courseSystem Design

Combination Sum II

Combination Sum II

BacktrackingRecursion
MediumLeetCode #40
25 min

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

Example

Example 1:

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

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

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

Solution

This problem is a variation of Combination Sum where each number in the input array can be used only once, and the input array can contain duplicates. To handle this, we first sort the candidates. Then, in our backtracking function, we add a condition to skip over duplicate numbers to avoid duplicate combinations in the result.

Algorithm Steps

  • Sort the `candidates` array to handle duplicates.
  • Define a recursive function `backtrack(start, currentSum, currentCombination)`.
  • If `currentSum` equals `target`, a valid combination is found. Add it to the results.
  • If `currentSum` exceeds `target`, stop exploring this path.
  • Iterate from `start` to the end of `candidates`.
    • **Crucial step for duplicates:** If `i > start` and `candidates[i]` is the same as `candidates[i-1]`, continue to the next iteration to avoid duplicate combinations.
    • Add `candidates[i]` to `currentCombination`.
    • Recursively call `backtrack(i + 1, currentSum + candidates[i], currentCombination)`. Note `i + 1` because each number can be used only once.
    • Backtrack: remove `candidates[i]` from `currentCombination`.
  • Initial call: `backtrack(0, 0, [])`.

Combination Sum II Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Candidates (sorted)

Target

1
1
2
5
6
7
10
8

Combination

Sum

[]
0

Unique Combinations

No solutions found yet...

Combination Sum II Solution

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        res = []

        def backtrack(cur, pos, target):
            if target == 0:
                res.append(cur.copy())
            if target <= 0:
                return

            prev = -1
            for i in range(pos, len(candidates)):
                if candidates[i] == prev:
                    continue
                cur.append(candidates[i])
                backtrack(cur, i + 1, target - candidates[i])
                cur.pop()
                prev = candidates[i]
        
        backtrack([], 0, target)
        return res