Solutions

# Sort, backtracking, skip duplicates and recurse.

# O(n * 2^n) time, O(n) space
def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    res = []

    # Sort the array so that we can skip duplicates candidates
    candidates.sort()

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

        # include current candidates (and recursively all subsequent candidates with the same value)
        cur.append(candidates[i])
        dfs(cur, total + candidates[i], i+1)

        # backtrack, removing current element
        cur.pop()
        # skip all candidates that are equal to current one
        while i + 1 < len(candidates) and candidates[i] == candidates[i+1]:
            i += 1
        # recurse from next different candidate 
        dfs(cur, total, i+1)

    dfs([], 0, 0)
    return res


# Alternative version
def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    candidates.sort()
    rec(candidates, target, [], res)
    return res

def rec(nums, target, curr, res):
    if target == 0:
        res.append(curr)
        return 
    elif target < 0:
        return
    else:
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            rec(nums[i+1:], target-nums[i], curr + [nums[i]], res)