Algorithm Notes
Summary: Combination Sum — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.
Big-O Guide
Source
"""
Combination Sum (LeetCode 39)
Given an array of distinct integers candidates and a target integer target,
return a list of all unique combinations of candidates where the chosen
numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times.
All solutions must be unique and use only numbers from the given candidate set.
"""
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def backtrack(start: int, path: List[int], total: int):
if total == target:
res.append(path[:])
return
if total > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, total + candidates[i])
path.pop()
backtrack(0, [], 0)
return res
def demo() -> str:
s = Solution()
result = s.combinationSum([2, 3, 6, 7], 7)
return str(result)