Combination Sum

Backtracking

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidateswhere 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.

For example:

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.

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

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

Thought Process

• When target == 0 is when we append to the solution list and backtrack. We also backtrack when target < 0, as this means the number we subtracted was too big and this number will not be a part of our solution set.

• Since the same number can be used an unlimited amount, in our for loop we just keep looping with "i" being the index. This accomodates for the same number being able to be used unlimited amounts.

  • Why this works is because we pop the element at the end and the "i" increments anyways in our for loop so this searches through the other numbers as well even though we aren't directly incrementing the pointer in our recursion.

Solution

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        soln = []
        self.helper(candidates, target, 0, [], soln)
        return soln
    
    def helper(self, candidates, target, index, sums, soln):
        if target == 0:
            soln.append(list(sums))
            return
        elif target < 0: #if we subtract too large of a number
            return
        
        for i in range(index, len(candidates)):
            sums.append(candidates[i])
            self.helper(candidates, target - candidates[i], i, sums, soln)
            sums.pop()

Key Points

• Using the for-loop, in our recursion method we can use "i" as the index to account for the number being used multiple times.

  • f

• "Tagret - candidates[i]" is what we use in our recursion method and what we use to stop DFS/begin backtracking when target == 0 or target < 0.

Time Complexity

• Time: $O(n^t)$ where n is the input list (candidates) and t is the target. This is the worst case because assuming that each recursive step we go over all existing candidates gives us base N and we can possibly go as deep as target in our recursive calls (if candidates are all 1's or close to 1), so power of target.

• Space: $O(target)$ becuase say all of our candidates are all 1's, then the recusrion stack will use the space equal to target (i.e. if target is 5 and we have candiates of [1,1,1] then we have 1+1+1+1+1, 1+1+1+1+1, and 1+1+1+1+1 for the 3 one's in the array).