Given an array of distinct integers candidates and a 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.
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.
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500
For the DP approach we create an array of size target+1 where each element i is a list of all candadiates where sum is equal to i. The time complexity of this solution is O(N * M^2) and the space complexity is O(M) where N is the length of candidates and M is the target.
def combinationSum(candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
:Time Complexity: O(N * M)
:Space Complexity: O(M)
"""
dp = [[] for _ in range(target + 1)]
dp[0] = [[]]
for c in candidates:
for i in range(1, target + 1):
if i - c >= 0:
for ans in dp[i - c]:
dp[i].append(ans + [c])
return dp[-1]