sub_set_sum.py

"""
Given an input array  and target sum, find all possible ways the elements of the array can be added upto get target
sub_set_sum([10, 7, 5, 18, 12, 20, 15], 35) =>

([15, 22, 14, 26, 32, 9, 16, 8], 53) =>
    8    9   14   22
    8   14   15   16
   15   16   22
   http://ideone.com/ZpDAXJ
"""

import unittest

def find_all_possible(curr_sum, target, nums):
    possible = []
    for i in range(len(nums)):
        if curr_sum + nums[i] <= target:
            possible.append(nums[i])
    return possible


def all_possible_sets_recursive(nums, curr_sum, target, sets, all_possible):
    if curr_sum == target:
        all_possible.append(sets)
        return sets

    possible = find_all_possible(curr_sum, target, nums)
    for i in range(len(possible)):
        sets.append(possible[i])
        sets = all_possible_sets_recursive(possible[i+1:], curr_sum + possible[i], target, sets, all_possible)
        sets = sets[:-1]
    return sets


def all_possible_subsets(nums, t):
    all_possible = []
    all_possible_sets_recursive(nums, 0, t, [], all_possible)
    return all_possible


class TestAllPossibleSubSets(unittest.TestCase):
    def is_valid_subset(self, expected, actual):
        return expected == actual

    def test_find_all_possible_subsets(self):
        actual = all_possible_subsets([15, 22, 14, 26, 32, 9, 16, 8], 53)
        expected = [[15, 22, 16], [15, 14, 16, 8], [22, 14, 9, 8]]
        self.assertEqual(self.is_valid_subset(expected, actual), True)
        actual = all_possible_subsets([10, 7, 5, 18, 12, 20, 15], 35)
        expected = [[10, 7, 18], [10, 5, 20], [5, 18, 12], [20, 15]]
        self.assertEqual(self.is_valid_subset(expected, actual), True)


if __name__ == "__main__":
    unittest.main()