Similar to the second solution and slightly faster (not sure why, ~35ms)
def combinationSum3(self, k, n, pres = [, , , , , , , , ]):
if k == 1:
return [pre for pre in pres if sum(pre) == n]
return self.combinationSum3(k-1, n, [pre+[d] for pre in pres
for d in range(pre[-1], 10)
if d not in pre and sum(pre)+d<=n])
nice solution! I also wonder about a more detailed explanation about the i<=n/k condition. I realize it is definitely correct and it is to save us from producing duplicate combo that are only different in order. And it is also easy to see that when k=2. but when k>2, I'm having some trouble wrapping my head around it. thanks a lot!