The Blind 75 Leetcode Series: Combination Sum

Photo by Chris Ried on Unsplash

Today, we will be working on Combination Sum.

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

We have an array of integers with each element being unique, and a target we are trying to match by adding up numbers in the array. The same numbers can be picked multiple times, and as long as one of the numbers is different between two answers, both answers are considered unique. We want to find all unique combinations to sum to the target number.

From the constraints, there’s always some element(s) in the array and we are guaranteed to have only integers in the array and the target. It’s not guaranteed to find at least 1 combination that sums to the target, so answer can be empty. Also, all elements in the array are positive.

Let’s take one of the examples given:

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.

In theory, [2,2,3] and [2,3,2] are both answers. Since they consist of the same numbers, they only count as one answer.

Since we are doing a summation, we can think of ways to build it up from these base numbers in the array. In the example above, it would be 2, 3, 6, and 7. Because we can use the same numbers repeatedly, we run through iterations and add these numbers to the sums from last iteration, and check if answers are ≥ target.

base: [2, 3, 6, 7]
1st iteration: [2+2=4, 2+3=5, 2+6=8, 2+7=9, 3+2=5, 3+3=6, 3+6=7, 3+7=10, 6+2=8, 6+3=9, 6+6=12, 6+7=13, 7+2=9, 7+3=10, 7+6=13, 7+7=14]
so...[4, 5, 8, 9, 5, 6, 7, 10, 8, 9, 12, 13, 9, 10, 13, 14]
and take out the repetitive ones:
[4, 5, 6, 7, 8, 9, 10, 12, 13, 14]
take out the ones greater than target, 7
[4, 5, 6, 7]

Several things to note here:

1. we are seeing some repeated sums. For example, 2+3 = 3+2, so we only need to take one of them.
2. There are numbers already greater than target, we can ignore them. Because all elements are positive, adding positive numbers to a number already greater than target won’t do us any good, so we can ignore them.

This becomes a dynamic programming where we find all possible combinations and keep tracking them. For each iteration, we keep the record and use it for the next iteration.

We start with the base cases, using the example above, we keep track of [2, 3, 6, 7] and creates

{2: [[2]], 3: [[3]], 6: [[6]], 7: [[7]]}

With the 1st iteration, we sum each number of each of keys above, getting

{
 2: [[2]],
 3: [[3]],
 4: [[2, 2]],
 5: [[2, 3], [3, 2]],
 6: [[6], [3, 3]],
 7: [[7]]
}
new_values = [4, 5, 6]

We can ignore everything that is greater than the target 7here as there’s no need to track them.

With the 2nd iteration, we now take these new_values, sum with [2, 3, 6, 7] each again.

{
 2: [[2]],
 3: [[3]],
 4: [[2, 2]],
 5: [[2, 3], [3, 2]],
 6: [[6], [3, 3], [2, 2, 2]],
 7: [[7], [2, 2, 3], [2, 3, 2], [3, 2, 2]]
}
new_values = []

There is no more new_values that is ≤ target, so we can abort and get target’s sums in the tracker. 7: [[7], [2, 2, 3], [2, 3, 2], [3, 2, 2]]

Then we need to take out the duplicates like [2, 2, 3] & [2, 3, 2]. A simple way is to sort each list and then do a set on them.

set(tuple(sorted(x)) for x in tracker.get(target, []))
# tracker is the dict above.

So, putting everything together, we have

def combinationSum(candidates, targe):
    last_iter = candidates  # initializing the values to sum with the candidates.
    tracker = {i: [[i]] for i in candidates}  # initialize tracker with candidates
    new_iter = []  # this is the new_values above
    while last_iter:  # keep summing until all values in last_iter is > target
        for i in candidates:
            for j in last_iter:
                if i + j <= target:
                    if i+j in tracker:
                        tracker[i+j].extend([k+[i] for k in tracker[j]])
                    else:
                        tracker[i+j] = [k+[i] for k in tracker[j]]
                    new_iter.append(i+j)
        # get a new set of values to sum up with & reset new_values
        last_iter = new_iter
        new_iter = []
    # dedupe        
    result = set(tuple(sorted(x)) for x in tracker.get(target, []))
    return result

The time complexity would be O(n * c), where n is the average length of last_iter, and c is the length of candidates. This is a bit complicated, since the last_iter keeps changing every iteration, we can only take an average of all occasions. As we keep summing the values in last_iter with candidates , the double for-loop creates this time complexity. We actually also have to deal with the dedupe at the end, but the for-loops should trump that.

Now, the code is actually quite dirty. We can try to improve it.

Currently, we use the candidates as base and keep looping through it to find next iteration of sums, but essentially, we just want to get to the target , so we can just create a for-loop from 0 to the target, then check if there’s any combination existing.

Next, a problem here is the dupes. We want to find a way to eliminate [2,3,2] at the spot when [2,2,3] is already present.

We can sort the candidates in ascending order, so we know that we should find [2, 2, 3] before we get to [2, 3, 2], so we can say “if our candidate is smaller than the last element seen in last combination, we can ignore it”

Third, we can eliminate the if-condition to check if the element exists in the dictionary by using a defaultdict

Now put this to code again:

def combinationSum(candidates, target):
    candidates.sort()
    tracker = defaultdict(list)
    for i in range(1, target + 1):
        for j in candidates:
            # no way this condition satisfies, no need to track
            if i < j:
                continue
            # candidate itself is a combination, track the candidate
            elif i == j:
                tracker[i].append([j])
            else:
                # only if candidate > last element in the combination of tracker[i - candidate] will we record it
                for combo in tracker[i - j]:
                    if combo[-1] <= j:
                        tracker[i].append(combo + [j])
    return tracker[target]

Much cleaner, isn’t it?

This is still a dynamic programming approach, and time complexity stays the same.

What if we have yet another way to tackle the problem?

We used the dynamic programming approach to “build up” from lower number. Can we “traverse down” from the target instead?

We introduce the backtracking approach using depth-first search (dfs), where we still continuously loop through the candidates, and subtract target from a candidate before we feed the new number to the function again.

Since we are recursively calling the function, we need a base condition. We are subtracting candidates from target repeatedly, so it’s intuitive to check for the value of target. If target < 0, we’ve hit the condition where the sum is greater than the target, so we return. If target == 0, we know we found a combination we want, so we track it and then return.

def combinationSum(candidates, targe):
    combinations = []
    # pass in initial values (empty lists)
    self.recursive(candidates, target, [], combinations)
    return combinations
def recursive(self, candidates, target, path, combinations):
    # the sum is now greater than target, ignore
    if target < 0:
        return
    # sum is exactly what target is, record the combination
    elif target == 0:
        combinations.append(path)
        return 
    else:
        # for each candidate, subtract target from it, add the candidate to the path, and pass the rest of the candidates to the function again
        for i in range(len(candidates)):
            self.recursive(candidates[i:], target - candidates[i], path +[candidates[i]], combinations)

The key here is the last line. We have to make sure we track these numbers (and lists) correctly. Write out some examples to help yourself getting the right numbers when whiteboarding.

What ‘s the time complexity? For backtracking, this post explains it well. Simply put, we know that the traverse will take the longest if the the candidate is smallest. (Ex. target =7, candidate=2, then we traverse 4 times (2+2+2+2) before exceeding target. candidate=3, traverse 3 times only (3+3+3), so the worst case is 4 times). Then for each candidate, we either pick it or don’t, so each candidate’s selection is 2^n, combining with the number of traversal, we have O(2^(target/smallest candidate)).

Here we go! This is a quite complicated problem. Thanks for following until the end! You are doing great! Another problem down!

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz