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:
-
nums.length
-
nums[i]
-
target
- 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 , where is the number of elements in nums
, is the target
, and is the minimum value in nums
. This is because each node in the recursion tree can have branches, and the height of the tree can grow up to . Therefore, the total number of nodes in such a tree is bounded by .
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 numbers. Since we know the answer to the subproblems formed by subtracting each of the numbers from thetarget
, 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]
andtarget=6
, we know that can be generated in two ways, i.e., and . Now, when we try to generate , we know that one way to generate it is using and . For this, the algorithm will try to generate 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 , where is the target
value. Each cell of our table, dp[i]
, represents the combination to make the target value
using elements from nums
.
First, for target , we add “[ ]” in dp[0]
because there is only one way to make a target of by using none of the available options. After this, for any target and each 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.