Combination Sum

def combination_sum_opt(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    candidates.sort()
    def backtrack(remain, stack, start):
        if remain == 0:
            res.append(list(stack))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain: break
            stack.append(candidates[i])
            backtrack(remain - candidates[i], stack, i)
            stack.pop()
    backtrack(target, [], 0)
    return res

def combination_sum_brute(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    def dfs(i, cur, total):
        if total == target:
            res.append(cur.copy())
            return
        if i >= len(candidates) or total > target:
            return
        cur.append(candidates[i])
        dfs(i, cur, total + candidates[i])
        cur.pop()
        dfs(i + 1, cur, total)
    dfs(0, [], 0)
    return res