I am trying to find a space and time efficient way to calculate the number of ways to partition a set of integers {1, 2, …, N} into two partitions such sums of integers in the two partitions is equal. I have started with a brute force approach that seems to give me correct results.
from itertools import combinations def f(n): s = set([i+1 for i in range(n)]) valid_partitions = [] for i in range(1,n): combos = combinations(s,i) for c in combos: p1 = frozenset(c) p2 = set(range(1,n+1)) - p1 p2 = frozenset(p2) if sum(p1) == sum(p2): valid_partitions.append(frozenset((p1,p2))) return len(set(valid_partitions))
Also, since I am checking every way to partition {1,2,…,N} into two non-empty sets, is it correct to say that the Big O time complexity of this approach is S(N,2)
(Stirling Number of the Second Kind)? Also, how would I evaluate the Big O space complexity of this approach? Is there a better approach I can take? I would appreciate any help! Thanks