39. Combination Sum#

Difficulty: Medium

Link to Problem: To see the Combination Sum problem on LeetCode, click here!

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 the target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the 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.

Constraints:

  • 1 <= candidates.length <= 30

  • 2 <= candidates[i] <= 40

  • All elements of candidates are distinct.

  • 1 <= target <= 40

Probelm Explanation:#

The problem is to find all unique combinations of numbers from a given array (candidates) such that their sum equals a target number. Here are the details of the problem:

  • You are given an array of distinct integers called “candidates.”

  • You are also given a target integer called “target.”

The goal is to find all unique combinations of numbers from the candidates array where the sum of the selected numbers is equal to the target. You can use the same number from the candidates array an unlimited number of times. A combination is considered unique if it has a different frequency (i.e., a different number of occurrences) of at least one chosen number compared to other combinations.

For example:

Example 1:

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

In this example, there are two unique combinations that sum up to the target:

  • 2 + 2 + 3 = 7

  • 7 = 7

Example 2:

Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Here, there are three unique combinations that sum up to the target.

Example 3:

Input: candidates = [2], target = 1
Output: []

In this case, there are no combinations that can be formed from the candidates to reach the target of 1, so the output is an empty list.

The problem asks you to find and return these combinations in any order.

The constraints for this problem include the length of the candidates array, the values of candidates, and the target value.

Solution:#

Here’s a Python function to implement this algorithm:

def combinationSum(candidates, target):
    # Define a recursive DFS function to find combinations
    def dfs(remaining, start, path):
        # If the remaining target is 0, we found a valid combination
        if remaining == 0:
            result.append(path)
            return
        # If the remaining target is negative, this path is invalid
        if remaining < 0:
            return
        # Iterate through candidates starting from 'start' to avoid duplicates
        for i in range(start, len(candidates)):
            # Explore the current candidate by subtracting it from the remaining target
            # Add the current candidate to the path
            dfs(remaining - candidates[i], i, path + [candidates[i]])

    result = []  # Initialize an empty list to store the result
    candidates.sort()  # Sort the candidates for deduplication and early stopping
    dfs(target, 0, [])  # Start the DFS from the target value with an empty path
    return result  # Return the list of unique combinations

Explanation:#

The combinationSum function takes an array of distinct integers candidates and a target integer target. It returns a list of all unique combinations of candidates where the chosen numbers sum to the target. Each number in the candidates array can be used an unlimited number of times.

Here’s an overview of how the code works:

  1. The combinationSum function is defined, and it takes two arguments: candidates and target.

  2. Inside the function, there is a nested helper function called backtrack. This function is responsible for the actual combination generation using a recursive approach.

  3. The backtrack function is called with three arguments: start, target, and path. The start variable helps keep track of the current index in the candidates array, target keeps track of the remaining sum to be achieved, and path is a list that stores the current combination.

  4. Within the backtrack function, there are three main conditional statements:

    • If target becomes zero, it means we have found a combination that sums up to the target, so we add path to the result list.

    • If target becomes negative, it means the current combination doesn’t work, so we return without doing anything.

    • Otherwise, we enter a loop that iterates over the candidates array, starting from the current index start.

  5. In the loop, the backtrack function is called recursively with the updated target and path after including the current candidate. This process explores different combinations by considering the current candidate or moving to the next candidate.

  6. After the loop completes, the result list contains all unique combinations that sum to the target.

  7. The candidates array is sorted to optimize the search. Sorting helps in avoiding unnecessary recursive branches and reduces the number of explored combinations.

  8. Finally, the backtrack function is initially called from the combinationSum function with start set to 0, target set to the original target value, and an empty path. The result is returned as a list of unique combinations.

The code includes a few example cases to demonstrate how the function works with different inputs.

Test cases:#

Here’s how you can use this solution:

# Example 1: 

# Example 1
candidates1 = [2, 3, 6, 7]
target1 = 7
print(combinationSum(candidates1, target1))  # Output: [[2, 2, 3], [7]]

[[2, 2, 3], [7]]

# Example 2
candidates2 = [2, 3, 5]
target2 = 8
print(combinationSum(candidates2, target2))  # Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

# Example 3
candidates3 = [2]
target3 = 1
print(combinationSum(candidates3, target3))  # Output: []

[]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the combinationSum function.

Time Complexity: The time complexity of this function is influenced by the number of recursive calls made by the backtrack function and the amount of work done within each call. In the worst case, the function will explore all possible combinations.

The worst-case scenario occurs when we have many combinations to reach the target. The time complexity can be expressed as \(O(2^n)\), where ‘n’ is the maximum number of recursive calls. In this context, ‘n’ corresponds to the number of elements in the candidates list, and it may be up to 30 (as per the constraints). However, the actual number of combinations explored is generally much smaller because we eliminate branches when the target becomes negative, and we skip over candidates that cannot lead to a solution. The sorting step also helps to optimize the search.

Space Complexity: The space complexity is determined by the auxiliary space used for storing the results and the stack space for the recursive calls.

  1. The space required for the result list can be up to \(O(2^n)\) in the worst case because each combination is stored.

  2. The stack space for the recursive calls can also be up to O(n) in the worst case, where ‘n’ is the number of elements in the candidates list.

Therefore, the overall space complexity of the function is \(O(2^n + n)\). However, in practice, the space used for the results list is often the dominant factor, and the actual space used may be much smaller than 2^n because not all combinations are explored.

In summary, the time complexity is exponential but typically smaller in practice due to optimization, and the space complexity is influenced by the number of results and the depth of the recursion.

Challenging Exercises:#

  1. Find the Number of Unique Combinations: Instead of listing all unique combinations, modify the function to return the count of unique combinations that sum to the target.

  2. Combinations with a Maximum Value: Add a maximum value constraint for each combination, so they cannot exceed a certain value. Modify the code to find combinations respecting this constraint.