☀️Combination Sum

Medium | Grind 75 | Tuesday 02, August 2022

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.

It is guaranteed 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

• 1 <= candidates[i] <= 200

• All elements of candidates are distinct.

• 1 <= target <= 500

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: []

SOLUTION

The question is pretty simple. Given a target value and an array of unique integers, we need to find the different unique combinations whose sum is equal to the target. I am not sure if there is a more elegant solution but my idea to solve this was to iterate over all the possible combinations that are either close to the target or the exact target amount (a basic backtracking problem).

Example 1: We will take the first element (2 in this case) and calculate all the combinations when it starts with 2. A few of the combinations when you start with element 2 are:

[2,2,2,2], [2,2,2,3], [2,2,2,6], [2,2,2,7], [2,2,3,3]....[2,7,7,7]

Once we run through all possible combinations starting with element 2, we will look at the second element 3. This time, we do not need to consider 2 anymore since any valid combinations will have been covered when calculating using 2. We will keep repeating this for every single element in the array.

When we are calculating the combinations, we need to keep track of whether a combination is valid or not. If it is valid, then we will add it to our final list containing all the unique combinations. This can be achieved in the code by checking if the target - current element is 0 or not. Every time, we call the recursive function, we will first subtract the target by the current element and send that as our target. If that subtraction leads to 0, then we have found a valid combination. If the target is less than 0, then we know looking at more elements won't help, so we return, signifying it is not a valid combination.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = [] # store all the valid unique combinations
        path = [] # current path we are assessing 
        self.search(candidates, target, path, results) 
        
        return results
    
    def search(self, candidates, target, path, results): 
        ''' iterate over every possible combinations in the candidates list'''
        
        if target == 0:  # if target is 0, we know this is a valid combination so we add to our results
            results.append(path)

        elif target < 0: # invalid combination
            return 

        else: 
            # recursive call to iterate over every possible combinations. 
            for i in range(len(candidates)): 
                self.search(candidates[i:], target-candidates[i], path+[candidates[i]], results)

TIME AND SPACE

TIME: TBD (my head hurts thinking about this)

SPACE: TBD