Combination Sum

Medium

Snap

2 views

Topics:

ArraysRecursion

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 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.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

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

Example 3:

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

Constraints:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Combination Sum

Medium

Snap

2 views

Topics:

ArraysRecursion

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 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.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

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

Example 3:

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

Constraints:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `candidates` array contain negative numbers? What is the range of values for the numbers in the `candidates` array and the `target`?
What should I return if no combinations sum up to the `target`?
The problem description mentions 'unique combinations'. Does the order of numbers within a combination matter (e.g., is [2, 2, 3] the same as [2, 3, 2])? Does the order of combinations in the output list matter?
Are the numbers in `candidates` guaranteed to be distinct? If not, how should I handle duplicate numbers in the `candidates` array?
Can the target be zero? Can the candidates array be empty?

Brute Force Solution

Approach

The brute force approach for the Combination Sum problem is like trying every single possible combination of numbers to see if any of them add up to the target. We explore all branches, even if they seem unlikely, until we find all the valid combinations. It's like rummaging through every corner of a room to find a specific item.

Here's how the algorithm would work step-by-step:

Start by picking the first number from our set of available numbers.
See if this first number is already equal to the target. If it is, we have found one combination!
If the first number is smaller than the target, subtract it from the target and try to find other numbers that, when added to this first number, will equal the target.
To do this, we can pick the first number *again* and see if that gets us closer to the (remaining) target.
We can also pick the second number from our set, or the third number, and so on. For each number we pick, we subtract it from the remaining target.
We keep going, picking numbers and subtracting them, until either the remaining target becomes zero (meaning we found a combination that works!) or the remaining target becomes negative (meaning this combination doesn't work and we need to try something else).
Whenever the remaining target goes negative, we go back (backtrack) to a previous step and try a different number from our set.
We repeat this process, trying every single possible combination of numbers, until we have explored all the possibilities.
Collect all the valid combinations that added up to the target value.

Code Implementation

def combination_sum_brute_force(candidates, target):
    results = []
    def backtrack(remaining_target, combination, start_index):
        # If we've found a valid combination
        if remaining_target == 0:
            results.append(combination[:])
            return

        # If we've overshot, this combination is invalid
        if remaining_target < 0:
            return

        # Iterate through the candidates, starting at start_index
        for i in range(start_index, len(candidates)):
            candidate = candidates[i]

            # Add the current candidate to the combination
            combination.append(candidate)

            # Recursively call backtrack with updated target
            # Allow duplicates by staying on same index
            backtrack(remaining_target - candidate, combination, i)

            # Backtrack: Remove the last added candidate
            # to explore other possibilities.
            combination.pop()

    backtrack(target, [], 0)
    return results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N^(T/M)) – The time complexity for Combination Sum, using the described brute force approach with recursion and backtracking, is exponential. Here, N represents the number of candidate numbers, T is the target value, and M is the minimum value within the candidate numbers. At each step, we explore all possible combinations by repeatedly choosing candidate numbers until the target is reached or exceeded, resulting in a tree-like exploration. The height of this tree can be roughly T/M, and at each node, we have N choices, leading to approximately O(N^(T/M)) operations in the worst-case scenario. Therefore, even though it's not a simple polynomial, the exponential nature makes it computationally expensive.

Space Complexity

O(target) – The space complexity is primarily determined by the depth of the recursion and the size of the temporary list used to store the current combination. In the worst-case scenario, where the smallest number in the candidates array is 1, the recursion could go as deep as the target value. Each recursive call adds a stack frame to the call stack. Additionally, a temporary list stores the current combination of numbers, and in the worst case, this list could also contain up to 'target' elements. Thus, the auxiliary space used is proportional to the target value, resulting in O(target) space complexity.

Optimal Solution

Approach

The best way to solve this problem is by systematically exploring possibilities and making smart choices to avoid redundant work. We'll use a method that builds up combinations step-by-step, ensuring we only consider valid solutions and avoid repeating the same combinations in different orders.

Here's how the algorithm would work step-by-step:

Begin with an empty combination.
Consider each number from the provided set of numbers as a potential addition to the current combination.
If adding the number brings the sum of the combination closer to the target, include it and explore further possibilities from that point. This helps to build valid combinations incrementally.
If adding the number exceeds the target, discard it and move on to the next number.
If adding the number perfectly reaches the target, save this combination as a solution.
To prevent duplicate combinations that have the same numbers in a different order, always consider numbers in non-decreasing order from the starting point. This means when you've used a number, you can use it again or move to the next larger number, but you should never go back to a smaller number.
Once you've explored all possibilities from a particular starting point, backtrack to explore other branches. This ensures you cover all possible combinations that sum to the target.
Continue this process until all possible combinations have been examined, building only valid solutions and avoiding duplicates.

Code Implementation

def combination_sum(candidates, target):    result_combinations = []
    def find_combinations(remaining_target, current_combination, start_index):
        # If target is reached, add combination
        if remaining_target == 0:
            result_combinations.append(current_combination[:])
            return
        #If target is negative, end search
        if remaining_target < 0:
            return

        # Iterate through the candidates
        for i in range(start_index, len(candidates)):            #Explore combinations using current candidate            current_combination.append(candidates[i])

            find_combinations(remaining_target - candidates[i], current_combination, i)

            #Backtrack and remove the last element
            current_combination.pop()

    find_combinations(target, [], 0)
    return result_combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N^(T/M)) – Let N be the number of candidates, T be the target value, and M be the minimum value among the candidates. The worst-case time complexity is exponential. The algorithm explores all possible combinations by recursively branching. In the worst case, we can repeatedly pick the smallest number (M) until we reach the target (T). The depth of the recursion can be T/M. At each step, we have N choices. Therefore, the time complexity can be approximated as O(N^(T/M)).

Space Complexity

O(target) – The algorithm uses a recursion stack to explore possible combinations. The maximum depth of the recursion is bounded by the target value, as each recursive call potentially adds a candidate number to the current combination until the target is reached or exceeded. Additionally, a temporary list is used to store the current combination being explored, and the maximum size of this list is also bounded by the target value. Therefore, the auxiliary space used by the recursion stack and the temporary list is proportional to the target value, resulting in a space complexity of O(target).

Edge Cases

Case	How to Handle
Null or empty candidates array	Return an empty list as there are no numbers to form combinations.
Target is zero	Return a list containing a single empty list, representing the only combination that sums to zero.
Target is negative	Return an empty list as no combinations of positive numbers can sum to a negative target.
Candidates array contains zero	Include zero in combinations as many times as needed to reach the target if zero is present in the candidates.
Candidates array contains negative numbers	The problem statement specifies distinct integers, but if negatives were allowed, consider that a number can be added and subtracted to reach the target; be sure to handle to avoid infinite recursion.
Large target value with small candidate values leading to deep recursion	Be aware of potential stack overflow errors with recursive solutions; consider iterative approaches if necessary.
No combination sums to the target	The backtracking algorithm will explore all possibilities and return an empty list if no valid combination is found.
Candidates array contains very large numbers causing potential integer overflow	Be mindful of potential integer overflow during summation and choose appropriate data types or add checks to prevent it.