Back tracking technique
either time we can choose pick cur_num or not pick cur_num
and we take advantage of the same list for fix space complexity
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(num, cur_sum, comb):
if cur_sum > n or len(comb) > k:
return
if cur_sum == n and len(comb) == k:
return ans.append(comb[:])
for i in range(num, 10):
comb.append(i)
backtrack(i + 1, cur_sum + i, comb)
comb.pop()
ans = []
backtrack(1, 0, [])
return ans
Back tracking technique either time we can choose pick cur_num or not pick cur_num and we take advantage of the same list for fix space complexity