# Find number of subsets with equal sum

• Given a number N ( N > 1), gives a set S = [1,2,..., N].
Divide S in two subsets such that S1 ∪ S2 = S and S1 ∩ S2 = Ø and return the number of subsets with equal sum.

Example:
Given N = 7, S = [1, 2, 3, 4, 5, 6, 7]. Return 2, since sum of [1, 6, 7] = sum of [2, 3, 4, 5].

• This post is deleted!

• It's quite easy to know the sum of each subset is half of the sum from 1to N which is ((1+N)*N)/2。We can use this num to subtract N to 1 one by one, if it current num is bigger than the number we want to subtract, we just go to next circle and subtract the smaller number untill the num is 0, erery time we implement subtracting, we can record the num we subtracted, which make up the answer. The complexity will be O(N).Sorry about my poor english.

• @ZhangShaojie Welcome to the new Discuss! Thanks for sharing your idea with us :D

• @ZhangShaojie Just find a method to improve this:if the current num is less than the num in 1-N that we want to subtract, this num is the las num in answer! Is is quicker.

• @ZhangShaojie Could you please give an example? An example illustrating the steps would be helpful for others to understand :)

• @1337c0d3r Take the N=7 as an example. (7*(1+7))/2=28 28/2=14 14-7=7 7>6,7-6=1 , 1<5 ,so 1is the last number.So answer is [1,6,7]，easy to know another subset

• Just a question. In the example above there are 2 subsets, but it is possible to be more ,right? Could you give me a example with more subsets?

• @elmirap Somewhat mislead by the description of "Divide S in two subsets ", if the sum of 1 to N is a odd number, it cannot be divided into two subsets, I think we can find the least divisor of the num , the divisor will be the number of subset. I'd like to write a program later.

• @1337c0d3r I think that the problem could be explained with more detail. It is not clear from the first reading, what is meant.
I was thinking on the problem and seems that something was lost in translation.
In my view the problem is the following :

Given a number N ( N > 1), gives a set S = [1,2,..., N].
Divide S in two subsets such that S1 ∪ S2 = S and S1 ∩ S2 = Ø and return the number of ways there are subsets with equal sum.

Example:
Given N = 7, S = [1, 2, 3, 4, 5, 6, 7].
since sum of [1, 6, 7] = sum of [2, 3, 4, 5]. - 1 way
sum [7] = [6,1] = [5 ,2] = [4,3] - 2 way

It is not the number of subsets with equal sum. Because with N = 7 there are more than 2 subsets with eq number
For example :
[1, 6, 7] = sum of [2, 3, 4, 5]
[1, 6, 3,4]] = sum of [2, 7, 5]
[1, 2,4, 7] = sum of [6,3, 5]
[7,3,4] = sumof[2,1,6,5]
......................................

• @elmirap Thanks for raising this question. I really doubt the original question meant this way as it is not intuitive at all.

If asked the number of ways you can partition an array with two equal subset sum, most people will think it as the number of subsets with equal sum.

@hackermonk Can you please clarify? For your example n=7, there seems to be more ways to partition it as @elmirap showed.

• This is the partition problem, which is known to be NP-hard. There is a pseudo-polynomial time dynamic programming algorithm. See Wikipedia

• ``````int equal_sum_sub_set(vector<int>& num)
{
int sum = 0;
for(int n : num) {
sum += n;
}
if((sum & 1) == 1) {
return 0;
}
sum >>= 1;
vector<int> dp(sum + 1, 0);
dp[0] = 1;
int current_sum = 0;
for (int i = 0; i < num.size(); i++)
{
current_sum += num[i];
for (int j = min(sum, current_sum); j >= num[i]; j--)
dp[j] += dp[j - num[i]];
}
return dp[sum];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.