-4

I'm working on a combinatorics problem where I need to compute how many ways the set {1, 2, ..., n} can be divided into two subsets with equal sum, such that every number from 1 to n is in exactly one of the two subsets. The two subsets are unordered (i.e., {A, B} is considered the same as {B, A}).

Constraints:

  • n is between 1 and 500.
  • Result must be modulo 10⁹ + 7.

Example:

For n = 7, the valid partitions are:

{1, 3, 4, 6} and {2, 5, 7} {1, 2, 5, 6} and {3, 4, 7} {1, 2, 4, 7} and {3, 5, 6} {1, 6, 7} and {2, 3, 4, 5}

So the answer is 4.

What I’ve tried:

I noticed the total sum S = n(n+1)/2, and if S is odd, the answer is 0. I also tried adapting a dynamic programming approach similar to the classic subset sum problem:

MOD = 10**9 + 7 n = 7 # Idea: dp[i][j] = number of ways to pick a subset from {1..i} with sum j dp = [[0] * (target + 1) for _ in range(n + 1)] # Initialize...

But I'm not sure how to:

  1. Avoid overcounting mirrored partitions.
  2. Efficiently handle the modulo math.
  3. Translate the total number of equal-sum partitions from this DP table.

Question:

How should I modify or complete this DP to correctly count unique equal-sum bipartitions of {1..n}? Is there a standard trick (e.g. halving final count, inclusion-exclusion, etc.) I should be using here?

Improve this question
2
  • 4
    Why did you tag c++ when there is no C++ involved in the body of the question? Commented Jun 7 at 23:43
  • 2
    Say you have a set of integers {x|a≤x≤b} and you need to count the number of subsets that sum to S. Would not the answer be count(a,b,S)=count(a+1,b,S)+count(a+1,b,S-a), with obvious termination conditions? Commented Jun 8 at 8:37

1 Answer 1

Reset to default
1

The sum of 1, ..., n is n * (n + 1) / 2 indeed. But if your numbers are not 1 to n, but could have gaps or duplicates, then this formula will not work. Let's be more agnostic and say that the sum is X

and the groups have the same sum, let's call it Y. The total number of the two groups is X, that is

2Y = X

Therefore you can compute all combinations and keep those whose sum is Y and number of items is lesser than n (this is only interesting if you can have negatives or 0 as items).

And check the criteria you also mentioned

Result must be modulo 10⁹ + 7.

whatever that means.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

The question is to count the number of combinations, not generate them. The result is a number and this number should be given mod 10**9+7, which among other things reduces problems with integer overflow.
Indeed, and this is a rather standard dynamic programming problem.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.