The Blind 75 Leetcode Series: Combination Sum

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 = 7Output: [[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 `7`here 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 combinationsdef 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!

--

--

More from Jonathan Chao

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry

Love podcasts or audiobooks? Learn on the go with our new app.

Jonathan Chao

219 Followers

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry