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 ...