Combination Sum

combination_sum.py

class Solution(object):

    combinations = set()

    def solve(self, arr, n):
        self.helper(0, [], 0, n, arr)
        return list(self.combinations)

    def helper(self, start_index, current_comb, current_sum, sum, arr):

        if start_index == len(arr):
            return

        if current_sum > sum:
            return

        if current_sum == sum:
            self.combinations.add(tuple(current_comb))

        self.helper(
            start_index,
            current_comb[:] + [arr[start_index]],
            current_sum + arr[start_index],
            sum, arr
        )

        self.helper(
            start_index + 1,
            current_comb[:],
            current_sum,
            sum, arr
        )


if __name__ == "__main__":
    a = [2, 4, 6, 8]
    n = 8
    ans = Solution().solve(a, n)
    print(ans)