in the combination sum problem we are given a list consisting of distinct integers we need to find all the combinations whose sum equals to target given we can use an element more than one time complexityaverage case on constraints 1 candidates length 30 2 candidatesi 40 all elements of candidates are distinct 1 target 40 a recursive function that searches for possible combinations backtracks in case of a bigger current combination value than the target value parameters previousindex last index from the previous search target the value we need to obtain by summing our integers in the path list answer a list of possible combinations path current combination candidates a list of integers we can use combinationsum2 3 5 8 2 2 2 2 2 3 3 3 5 combinationsum2 3 6 7 7 2 2 3 7 combinationsum8 2 3 0 1 traceback most recent call last recursionerror maximum recursion depth exceeded a recursive function that searches for possible combinations backtracks in case of a bigger current combination value than the target value parameters previous_index last index from the previous search target the value we need to obtain by summing our integers in the path list answer a list of possible combinations path current combination candidates a list of integers we can use combination_sum 2 3 5 8 2 2 2 2 2 3 3 3 5 combination_sum 2 3 6 7 7 2 2 3 7 combination_sum 8 2 3 0 1 traceback most recent call last recursionerror maximum recursion depth exceeded type list int type list int
def backtrack(
    candidates: list, path: list, answer: list, target: int, previous_index: int
) -> None:
    
    if target == 0:
        answer.append(path.copy())
    else:
        for index in range(previous_index, len(candidates)):
            if target >= candidates[index]:
                path.append(candidates[index])
                backtrack(candidates, path, answer, target - candidates[index], index)
                path.pop(len(path) - 1)


def combination_sum(candidates: list, target: int) -> list:
    
    path = []  
    answer = []  
    backtrack(candidates, path, answer, target, 0)
    return answer


def main() -> None:
    print(combination_sum([-8, 2.3, 0], 1))


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()