An explanation for the corresponding partition counting algorithm?

Question

I worked on some problems of programming algorithms and asked a question about one. The problem is the same as in this question: USACO: subsets (ineffective)

I managed to encode some (non-dynamic) solutions that were too slow for high N. I had to cheat a little and find some solutions on the Internet. It turns out that the fast algorithm is trivially simple, but even knowing the answer, I still can’t figure out how to move from the problem to the answer. I can see patterns in the way of forming subsets of equal amounts, but I don't see the connection between these patterns and the algorithmic solution.

Problem (link above):

Given a set of consecutive integers from 1 to N (1 <= N <= 39), how many ways can a set be divided into two subsets whose sums are identical? For example, {1,2,3} can be divided in one direction: {1,2} {3}.

For large sets, the answer is either 0 (when N * (N + 1) / 2 is odd) or is given by this simple algorithm:

arr = array of int with (N*(N+1)/4)+1 elements arr[0]=1 // all other elements initialized to 0 for i = 1 to N for j = N*(N+1) / 4 downto i add arr[ji] to arr[j] subsetpaircount = arr[N*(N+1)/4] / 2 

Again, I see how the algorithm works, I even inserted print statements so that I can “watch” how it works. I just don’t see how the operation of the algorithm is associated with the template in different ways, two-installed sections are generated.

The answer to a related question may be appropriate, but I can’t also relate how it works: "This is the same as finding the term coefficient coefficient x ^ 0 in the polynomial (x ^ 1 + 1 / x) (x ^ 2 + 1 / x ^ 2) ... (x ^ n + 1 / x ^ n) ...

Can someone clarify the link for me or point me to some reference materials that explain this particular problem? Thanks.

Answer 1

If the set S = {1,...,N} divided into two subsets with equal sums, this sum should be equal to half the sum S ; the sum of S is N(N+1)/2 , so the sum of each subset in the section must be N(N+1)/4 . It must also be an integer, so N(N+1)/2 must be even.

Thus, the question boils down to finding the number of subsets S whose sum is N(N+1)/4 . The total number of sections will be exactly half as many, since each section contains two such subsets, and none of the two sections has a subset.

That should be obvious.

Now we list the subsets of S that sum with k for any k and any set S Any such subset should have the greatest value, which should be an element of S The largest value must be either the largest element of S , or must be less than the largest element of S These two groups of subsets are different, so we can list them separately. Let me call the largest element S S max .

The second group is simple: these are simply subsets of S - { S max } that sum with k . We can find them by recursively calling a subset of lister. But the first group is almost as simple: each set in the group includes S max , and the rest of its elements are a set from S - { S max } , which adds up to k - S max , which again can be listed recursively. To complete the recursion, we note that if S is an empty set, then if k = 0 , then there is only one qualification subset (the empty set itself), and if k is not equal to 0, then there are no defining subsets. Each recursion removes one element from S , so ultimately the termination condition must be reached.

It should be clear that the subsets of S that will be used by the recursive function indicated above are just numbers from 1 to S max , so we can get rid of S altogether and write the recursion as follows:

Subsets(min, max, k) =
Subsets(min, max - 1, k)
⋃ { {max, P} | P ∈ Subsets(min, max - 1, k - max) }


But we only need to count the number of partitions, so we can simplify this a bit:

Count_Subsets(min, max, k) =
Count_Subsets(min, max - 1, k)
+ Count_Subsets(min, max - 1, k - max)


We need to complete the recursion by adding the final condition:

If min > max, Count_Subsets(min, max, k) = 1 if k = 0; otherwise 0

(Actually, just showing that recursion means that the value will be 1 when k decreases to 0 , and 0 if k less than 0 , so we can make the termination condition happen much earlier.)

This gives us a simple recursion for counting. But since he calls himself twice, it would be better to work backwards ("dynamic programming"). We need to calculate Count_Subsets(1, N, N*(N+1)/4) , which will require us to calculate the values ​​of Count_Subsets(1, max, k) for all max values ​​from 1 to N and from all k values ​​from 0 to N * (N + 1) / 4. We do this starting from max = 0 and working until we reach min = N. And this is exactly what your algorithm does; i is max , and an array is a set of values ​​for k from 0 to N(N+1)/4 .

By the way, as follows from the above description, a[j] should be increased by a[j - i] , and not by a[j - 1]

Answer 2

I think there might be an error in your pseudo code that causes confusion. I would expect the line

 add arr[j-1] to arr[j] 

be

 add arr[ji] to arr[j] 

Assuming this is so, then the way to think about this problem is that at the beginning of each iteration of the loop over i, the arr [j] array contains the number of ways to select a subset of integers 1, 2, ..., i-1, so the sum of the selected integers is j.

When you start, i = 1, so the only choice of a subset is an empty subset with a sum of 1.

This is why arr [0] = 1 (representing the use of an empty subset to get the total number 0), and all other entries are 0 (since there is no way to get a nonzero sum).

From now on, each iteration pass considers adding the number i to the subset. The number of ways to get the sum j will depend on whether I am turned on or not.

If I'm not in the number, then we have the same number of ways as before (ie arr [j]).

If I am included, then in order to have a sum j including i, we must add I to all subsets 1, ..., i-1 that have a total number ji. By design, our array contains exactly this number, if we look at the ji index.

Thus, the total number of ways to obtain the sum j becomes arr [j] + arr [ji].

When the loop I complete, arr gives you the number of ways to select a subset and get any amount you want. We know that the sum 1,2, ..., n is n * (n-1) / 2, therefore, if we count how many subsets reach half of this value, we count the partitions into equal sums.

In fact, this is a 2-fold recalculation, because it calculates {1,2} / {3] and {3} / {1,2} as separate solutions, so the final answer is divided by 2.