Here is my solution for this problem in Python3, some questions I have in the comments.
Problem link: https://leetcode.com/problems/combination-sum/description/
Solution:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
out = []
comb = []
# sort candidates
candidates.sort()
def search(tgt, cands, comb):
if tgt < 0 or (not cands):
return False
if tgt == 0:
tgt = target # restart target
out.append(list(comb))
# add the new combo
comb = [] # restart combo
return True
# try adding the first one
cand = cands[0]
comb.append(cand)
tgt -= cand
search(tgt, cands, comb)
# backtrack
tgt += cand
comb.pop()
# try moving to next cand
search(tgt, cands[1:], comb)
search(target, candidates, comb)
return out
Some questions I'd like feedback on:
- When I append results to my final `out` list, I have to wrap `comb` into a list to avoid reference issues. Is there a better way to do that?
- I was trying to avoid passing `comb` in the list of args to my `search` function as its scope could be global to the internal function. How do I do that efficiently? (I guess I can use `nonlocal` somewhere?)
- The solution is in the top 25% (or 38% if I omit the sorting of candidates). What can I do to improve the algo?
