Solution: Combination Sum

Let's solve the Combination Sum problem using the Dynamic Programming pattern.

Statement

Given an array of distinct integers, nums, and an integer, target, return a list of all unique combinations of nums where the chosen numbers sum up to the target. The combinations may be returned in any order.

An integer from nums may be chosen an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen integers is different.

Constraints:

  • 11 \leq nums.length 30\leq 30
  • 22 \leq nums[i] 40\leq 40
  • 11 \leq target 40\leq 40
  • All integers of nums are unique.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach to solve this problem would be to make all the possible combinations of nums or generate all subsets of nums that sum up to the required target.

This solution is very costly because the time complexity of achieving this is O(nt/m)O(n^{t/m}), where nn is the number of elements in nums, tt is the target, and mm is the minimum value in nums. This is because each node in the recursion tree can have nn branches, and the height of the tree can grow up to t/mt/m. Therefore, the total number of nodes in such a tree is bounded by nt/mn^{t/m}.

Optimized solution using dynamic programming

Because the recursive solution to this problem is very costly, let’s see if we can reduce this cost in any way. Dynamic programming helps us avoid recomputing the same subproblems. Now let’s analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.

  • Optimal substructure: Let’s say we want to find the solution to the problem of counting a value, target, given nn numbers. Since we know the answer to the nn subproblems formed by subtracting each of the nn numbers from the target, we can simply sum up the answer to these subproblems. This gives us the answer to our original problem. Therefore, this problem obeys the optimal substructure property.

  • Overlapping subproblems: The algorithm solves the same subproblems repeatedly, so it also has the second property of dynamic programming. For example, for nums=[2,3,4] and target=6, we know that 44 can be generated in two ways, i.e., 2+22+2 and 44. Now, when we try to generate 66, we know that one way to generate it is using 22 and 44. For this, the algorithm will try to generate 44 again even though we’ve already computed it.

Let’s look at the dynamic programming approach to solving this problem. We first create a table, dp, of size (t+1)(t+1), where tt is the target value. Each cell of our table, dp[i], represents the combination to make the target value ii using elements from nums.

First, for target i=0i=0, we add “[ ]” in dp[0] because there is only one way to make a target of 00 by using none of the available options. After this, for any target i>0i > 0 and each jthj^{th} number in nums, we only select this number if nums[j] <= i. After selecting a number nums[j], we traverse all combinations in dp[i-nums[j]] because each combination in that cell represents a combination that can sum up to target i after adding nums[j] to it. For each such combination, we append nums[j] to it, sort it to avoid redundancy, and check whether it already exists in dp[i]. If not, we append this combination to dp[i]. We repeat this process until we’ve processed all target values. Finally, the last cell of the table, dp[target], gives us the unique combinations of nums that make up the target.

Let’s look at the following illustration to get a better understanding of the algorithm:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.