algoadvance

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be used an unlimited number of times. Two combinations are unique if their frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1

Example 2

Example 3

Clarifying Questions

  1. Can the candidates list or the target be empty?
    • No, according to the problems it is implied that both will have valid values.
  2. Will the candidates list contain negative numbers or zeros?
    • No, it will contain only positive distinct integers.
  3. Can the solution set contain duplicate combinations?
    • No, each combination must be unique.

Strategy

We can use a backtracking approach to tackle this problem:

  1. Sort the candidates - This helps to stop early if the current sum exceeds the target.
  2. Backtracking - We recursively try adding each candidate to the current combination and backtrack if the sum exceeds the target or explore further if it doesn’t.
  3. Base Cases:
    • If the current sum becomes equal to the target, add the current combination to the result list.
    • If the current sum exceeds the target, stop further exploration.

Code

def combinationSum(candidates, target):
    def backtrack(start, current_combination, current_sum):
        # If the current sum equals the target, add the current combination to the result.
        if current_sum == target:
            result.append(list(current_combination))
            return
        # If the current sum exceeds the target, return.
        elif current_sum > target:
            return
        
        # Iterate over the candidates starting from `start` index to avoid duplicates.
        for i in range(start, len(candidates)):
            current_combination.append(candidates[i])
            backtrack(i, current_combination, current_sum + candidates[i])
            # Backtrack, remove the last added element
            current_combination.pop()
    
    candidates.sort()
    result = []
    backtrack(0, [], 0)
    return result

# Example usage:
print(combinationSum([2, 3, 6, 7], 7))  # Output: [[2, 2, 3], [7]]
print(combinationSum([2, 3, 5], 8))     # Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
print(combinationSum([2], 1))           # Output: []

Time Complexity

The time complexity is O(2^T/M), where T is the target sum and M is the minimal value among the candidates. This represents all the possible combinations that could sum up to target. The space complexity is proportional to the combination length and recursive call stack, i.e., O(T/M).

Try our interview co-pilot at AlgoAdvance.com