Problem Statement in English

You’re given an array of integers candidates and a target integer target. Each number in candidates may only be used once in the combination. Find all unique combinations in candidates where the candidate numbers sum to target. The solution set must not contain duplicate combinations.

Approach

We can solve this problem using a backtracking approach. The idea is to explore all possible combinations of the given candidates and check if they sum up to the target.

In order to do this, we will load nums into a hashmap to keep track of the count of each number. Then, we will sort the keys of the hashmap in descending order. This will allow us to explore larger numbers first, which can help in pruning the search space.

Next we will define a recursive function solve(i) that will take the index of the current number in the sorted keys. If adding the value at that index to the current sum does not exceed the target, we will include it in our temporary combination and recursively call solve(i) again to explore further combinations. If the current sum equals the target, we will add the temporary combination to our result list.

The reason we call the same function with the same index again is because we can use the same number multiple times as long as we have not exhausted its count in the hashmap. Once we have explored all possibilities with the current number, we will backtrack by removing it from the temporary combination and restoring its count in the hashmap.

Finally, we will call solve(0) to start exploring combinations from the first number in the sorted keys.

And we’re done!

Solution in Python


class Solution:
    def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
        hm = Counter(nums)

        keys = sorted(hm.keys(), reverse=True)

        N = len(keys)

        res = []
        temp = []
        s = 0
        
        def solve(i):
            nonlocal s, res, temp

            if s == target:
                res.append(temp.copy())
                return

            if i >= N:
                return
            
            k = keys[i]
            count = hm[k]

            if count and s + k <= target:
                s += k
                hm[k] -= 1
                temp.append(k)

                solve(i)

                s -= k
                hm[k] += 1
                temp.pop()

            solve(i + 1)

        solve(0)
        
        return res

Complexity

  • Time: $O(2^n)$
    Since we are exploring all possible combinations of the candidates, the time complexity is exponential in the worst case.

  • Space: $O(n)$
    Since we are using a temporary list to store the current combination, the space complexity is linear in the worst case.

Mistakes I Made

I recursed to the next index instead of the current index.

And we are done.