This problem could be directly solved directly using DFS.
from typing import List
from collections import defaultdict, deque
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.ans = []
candidates.sort()
self._helper(target, 0, candidates, [])
return self.ans
def _helper(self, target, start, candidates, path):
if target == 0:
self.ans.append(path[:])
return
elif target < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
self._helper(target - candidates[i], i, candidates, path)
path.pop()