Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations in candidates where the candidate numbers sum to target. The same number may be used an unlimited number of times.
Constraints:
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- All elements of candidates are distinct.
- 1 <= target <= 500
Examples:
Input: [2,3,6,7], 7
Output: [[2,2,3],[7]]
Explanation: There are two combinations that sum to 7: [2,2,3] and [7].
Solutions
Backtracking
Time: O(N^(T/M + 1))Space: O(T/M)
The backtracking approach is used to solve this problem. The idea is to start with an empty combination and add numbers from the candidates array one by one. If the sum of the current combination exceeds the target, we stop exploring this branch. If the sum equals the target, we add the current combination to the result list.
def combinationSum(candidates, target):
result = []
def backtrack(remain, comb, start):
if remain == 0:
result.append(list(comb))
return
elif remain < 0:
return
for i in range(start, len(candidates)):
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
backtrack(target, [], 0)
return resultFollow-up:
Combination Sum II
