Special subset sums: meta-testing
Problem 106
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:
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?
NOTE: This problem is related to Problem 103 and Problem 105.
def run(limit=12):
count = 0
for i in range(1, 3**limit):
lc = 0
rc = 0
lh = 0
rh = 0
t = i
j = 1
while t:
cur = t % 3
if (cur == 1):
lc += 1
lh = j
elif cur == 2:
rc += 1
rh = j
t /= 3
j += 1
if lc == 0 or rc == 0:
continue
if lh > rh:
continue
if lc != rc:
continue
l = []
r = []
t = i
j = 1
while t:
if t % 3 == 1:
l.append(j)
elif t % 3 == 2:
r.append(j)
t /= 3
j += 1
ok = False
for k in range(lc):
if l[k] > r[k]:
ok = True
break
if not ok:
continue
count += 1
return count