Statement

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

• S(B) S(C); that is, sums of subsets cannot be equal.
• If B contains more elements than C then S(B) S(C).

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

Solution

This problem is tightly related to problem 105, what is used here has been used to solve that problem.

The issue here is how to determine which are the combinations that are really needed to be checked and not spend checking combinations of subsets whose results wouldn't need to be calculated.

I'm going to work with subsets of indexes of the original set(0-index based), where if i < j then set[i] < set[j]. If we zip the indexes of each subset sorted in ascending order, and in every pair the first element is smaller than the second there's no need to test cause the second subset is greater than the first.

If there is at least a value in subset B that is higher than one is subset C then we can have an equality. If we have the combinations of all possible subsets to test it easy to determine which ones should be tested for equality and which ones can be discarded.

I just leave the ones which the first pair the first is smaller than the second in order not to have mirrored subsets.

from itertools import zip_longest, combinations, product
from functools import reduce
 
def filt_func(c1, c2):
    if c1[0] > c2[0]:
        return False
    return not reduce(lambda x, y: x and (y[0] < y[1]), zip_longest(sorted(c1), sorted(c2)), True)
 
def generator(n, k):
    s1 = combinations(range(n), k // 2)
    comb_total = []
    for comb1 in s1:
        left_nums = set(range(n)) - set(comb1)
        s2 = (c for c in combinations(left_nums, k // 2) if filt_func(comb1, c))
        comb_total.extend(product([comb1], s2))
    return comb_total
 
if __name__ == '__main__':
    result = sum(len(generator(12, i)) for i in range(4, 13, 2))
    print("The result is:", result)

The Python file is available for download: problem106.py.