Solutions

# Binary decision tree, backtracking. At each node, we have two choices: include the current candidate or exclude it.
# backtracking

# Time complexity: O(2^(n/M)) in the worst case, where n is the number of candidates and M is the minimum value among the candidates. This is because in the worst case, we can choose to include or exclude each candidate, leading to a binary tree of height n/M.
# Space complexity: O(n/M) in the worst case, where M is the minimum value among.
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    res = []

    def dfs(i: int, cur: list[int], total: int):
        if total == target:
            res.append(cur.copy())
            return
        elif total > target or i >= len(candidates):
            return

        # include candidates[i]
        cur.append(candidates[i])
        dfs(i, cur, total + candidates[i])

        # exclude candidates[i]
        cur.pop()
        dfs(i+1, cur, total)

    dfs(0, [], 0)
    return res

# Alternatively, we can use a for loop to iterate through the candidates instead of making two recursive calls for include and exclude. This can simplify the code and avoid the need for backtracking (pop).
def combinationSum1(candidates: list[int], target: int) -> list[list[int]]:
    out = []
    helper(candidates, target, 0, [], out)
    return out

def helper(nums: list[int], target: int, idx: int, curr: list[int], out: list[int]):
    if target < 0:
        return
    elif target == 0:
        out.append(curr)
    else:
        for i in range(idx, len(nums)):
            helper(nums, target - nums[i], i, curr + [nums[i]], out)