Given an array, try to divide them into two subsets, which makes two subsets sum equal. Constraints: values divisible by 3 and values divisible by 5 should be separated. Values that divisible by 3 and 5 should be in the divisible 5 subset.

subsetsum_constraints.py

class Solution:
    def find_equal_subsets(self, arr):
        """
        @param: arr: List[str]
        @return: Tuple
        """
        total = sum(arr)
        # if half subsets value exist
        if total % 2 != 0:
            return

        half = total / 2
        # a_set is 3n
        # b_set is 5n
        a_set, b_set, rest_list = self.constraint_filter(arr)
        a_subset, b_subset = self.subset_sum(rest_list, half - sum(a_set))
        if a_subset or b_subset:
            a_set += a_subset
            b_set += b_subset
            return a_set, b_set

    def constraint_filter(self, arr):
        rest = []
        a = []
        b = []
        for num in arr:
            if num % 5 == 0:
                b.append(num)
            elif num % 3 == 0:
                a.append(num)
            else:
                rest.append(num)
        return a, b, rest

    def subset_sum(self, arr, _sum):
        subset = []
        self.helper(arr, 0, _sum, subset, set())
        a = []
        b = []
        if subset:
            for i, num in enumerate(arr):
                # check if value has been choosed for a set
                if i in subset[0]:
                    a.append(num)
                else:
                    b.append(num)
        return a, b


    def helper(self, arr, pos, _sum, ret, temp):
        """
        select item indexes in arr to add to sum
        """
        if _sum == 0:
            ret.append(set(temp))
            return
        if _sum < 0 or pos >= len(arr):
            return
        for i in range(pos, len(arr)):
            temp.add(i)
            self.helper(arr, i + 1, _sum - arr[i], ret, temp)
            temp.remove(i)



if __name__ == '__main__':
    s = Solution()
    print(s.find_equal_subsets([1, 2, 3, 4, 5, 6, 7, 8]))
    #    ([3, 6, 1, 8], [5, 2, 4, 7])
    print(s.find_equal_subsets([15, 7, 8]))
    #    ([7, 8], [15])
    print(s.find_equal_subsets([15, 1, 2]))
    #     None