I've already asked this question before, but then I realized that wording was, unfortunately, quite confusing.
The statement of the problem is following:
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:
$1.$ $S(B) ≠ S(C$); that is, sums of subsets cannot be equal.
$2.$ 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?
Problem statement specifies that, if size of subset $B$ doesn't equal to the size of the subset $C$, then theirs sums will not be equal by default. So when testing set $A$ for the equality, we only consider subsets with the same size.
The main question is, for arbitrary set $A$ with size $n$ which satisfies conditions specified in the problem, how many pairs of subsets with the same size are needed to be tested? I couldn't have come up with purely mathematical solution myself, so I checked answers provided by the users in the discussion thread. A lot of them mentioned so called "grid method", for example, one of the posts:
First, some observations. If elements of the set are assigned in ascending order to subset $B$, subset $C$, or discarded, and every element of $B$ can be paired with an element of $C$ that was selected later, then B's sum will be smaller than $C$'s, and the comparison will not be necessary.
If you imagine a walk on a grid from upper left to lower right, where selecting an element for subset $B$ is like walking East, and selecting an element for subset $C$ is like walking South, and selecting an element for neither subset is effectively the same as selecting it for both (East, then South), then a walk that crosses the diagonal from north to south (with this direction being the first diagonal crossing) corresponds exactly to a subset pair that must be compared.
And one more
Clearly we only need to test equal size groups $(k)$. If we select $2k$ elements, we only need to test some partition of that into $2k$-size groups if there is an $m$-smallest number in the group with the smallest element that is bigger than the $m$-smallest number in the other group. This can be modeled as a path across a $k×k$ grid that crosses the diagonal, so we can use Catalan numbers $C_k$ (which count paths that don't cross the diagonal) and half the total number of paths across the grid to get the number of diagonal-crossing paths (half = given start direction).Then the selection of the initial $2k$ set is a binomial coefficient, and sum across values of $k$.
Can some explain what is this "grid" they are referring to? And how do you solve the problem using this method?