Combination Sum II

Problem Statement

You are given an array of integers candidates, which may contain duplicates, and a target integer target. Your task is to return a list of all unique combinations of candidates where the chosen numbers sum to target.

Each element from candidates may be chosen at most once within a combination. The solution set must not contain duplicate combinations.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

Example 1:

Input: candidates = [9,2,2,4,6,1,5], target = 8

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

Example 2:

Input: candidates = [1,2,3,4,5], target = 7

Output: [
  [1,2,4],
  [2,5],
  [3,4]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

You should aim for a solution with O(n \cdot 2^n) time and O(n) space, where n is the size of the input array.

Recommended Time and Space Complexity

You should aim for a solution with O(n \cdot 2^n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute-force solution would be to create a hash set, which is used to detect duplicates, to get combinations without duplicates. Can you think of a better way without using a hash set? Maybe you should sort the input array and observe the recursive calls that are responsible for duplicate combinations.

Hint 2

We can use backtracking to generate all combinations whose sum equals the given target. When the input array contains duplicate elements, it may result in duplicate combinations. To avoid this, we can sort the array. Why does sorting help? Because as we traverse the array from left to right, we form combinations with the current element. By skipping duplicate elements, we ensure that the same combinations are not repeated for identical elements. How can you implement this?

Hint 3

We recursively traverse the given array starting at index i, with a variable sum representing the sum of the picked elements. We explore elements from i to the end of the array and extend the recursive path if adding the current element results in sum <= target. When we processed an element, we backtrack and proceed to the next distinct element, skipping any similar elements in the middle to avoid duplicate combinations.

Solution

Brute Force

def combination_sum2_brute_force(candidates, target):
    res = set()
    candidates.sort()

    def generate_subsets(i, cur, total):
        if total == target:
            res.add(tuple(cur))
            return
        if total > target or i == len(candidates):
            return

        cur.append(candidates[i])
        generate_subsets(i + 1, cur, total + candidates[i])
        cur.pop()

        generate_subsets(i + 1, cur, total)

    generate_subsets(0, [], 0)
    return [list(combination) for combination in res]

Time complexity: O(n \cdot 2^n) Space complexity: O(n \cdot 2^n)

Backtracking

def combination_sum2_backtracking(candidates, target):
    res = []
    candidates.sort()

    def dfs(i, cur, total):
        if total == target:
            res.append(cur.copy())
            return
        if total > target or i == len(candidates):
            return

        cur.append(candidates[i])
        dfs(i + 1, cur, total + candidates[i])
        cur.pop()


        while i + 1 < len(candidates) and candidates[i] == candidates[i+1]:
            i += 1
        dfs(i + 1, cur, total)

    dfs(0, [], 0)
    return res

Time complexity: O(n \cdot 2^n) Space complexity: O(n)

Backtracking (Hash Map)

from collections import defaultdict

def combination_sum2_backtracking_hash_map(candidates, target):
    res = []
    count = defaultdict(int)
    cur = []
    a = []

    for num in candidates:
        if count[num] == 0:
            a.append(num)
        count[num] += 1

    def backtrack(candidates, target, cur, i):
        if target == 0:
            res.append(cur.copy())
            return
        if target < 0 or i >= len(candidates):
            return

        if count[candidates[i]] > 0:
            cur.append(candidates[i])
            count[candidates[i]] -= 1
            backtrack(candidates, target - candidates[i], cur, i)
            count[candidates[i]] += 1
            cur.pop()

        backtrack(candidates, target, cur, i + 1)
    backtrack(a, target, cur, 0)
    return res

Time complexity: O(n \cdot 2^n) Space complexity: O(n)

Backtracking (Optimal)

def combination_sum2_backtracking_optimal(candidates, target):
    res = []
    candidates.sort()

    def dfs(idx, path, cur):
        if cur == target:
            res.append(path.copy())
            return
        for i in range(idx, len(candidates)):
            if i > idx and candidates[i] == candidates[i - 1]:
                continue
            if cur + candidates[i] > target:
                break

            path.append(candidates[i])
            dfs(i + 1, path, cur + candidates[i])
            path.pop()

    dfs(0, [], 0)
    return res

Time complexity: O(n \cdot 2^n) Space complexity: O(n)