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