Given an array S of N positive integers, divide the array into two subsets such that the sums of subsets is maximum and equal. It is not necessary to include all the elements in the two subsets. Same element should not appear in both the subsets. The output of the program should be the maximum possible sum.
Constraints:
1 <= N <= 50
1 <= S[i] <= 1000
Sum of elements of S will not be greater than 1000.
Example:
Input:
5
2 3 4 1 6
Output:
8 {Explanation: The two subsets with maximum sum are [1,3,4] and [2,6]}
I found this question in one of the interview challenge. I used the traditional sum of subsets logic to find all the possible sum for n elements and then tried to reconstruct non-overlapping subsets for a sum from the 2D DP array. I couldn't get all tc to pass. Is there any better easier solution for this?
Can you provide the link for that problem?
It was an offline contest. The company had their own portal. Even I'm looking for a similar problem on codeforces/codechef or any other cp site.
I think this problem can be solved in O(N·totalsum2). Iterate over all possible sums and count the number of non-overlapping subsets with that sum. If the number of subsets is greater than or equal to 2 then you can divide the array into two subsets with sum equal to the current sum. You can count the number of non-overlapping subsets with sum equal to K in O(NK) using DP. This can be done with a slight modification to the standard 'count subsets with given sum' DP problem.
To see how to do it check here.
I think, solution from your link is wrong. Because when we do Array[Num + CurrentNum] + = 1, it can be that any Num's representation intersects with some Num + CurrentNum's already counted representations, and so we can't get new representation this way.
When we do Array[Num + CurrentNum] + = 1 we examine CurrentNum for the first time. So it is impossible to have already considered a subset with sum Num + CurrentNum that contains CurrentNum in it.
Thanks giorgosgiapis, that solution looks correct and easy to understand.
Not CurrentNum, but another element. For example, we process elements 10 2 3. After that we have Array[12] = 1 (10+2) and Array[13] = 1 (10+3). And next element is 1. Boom, we have Array[13] = 2. But this two representations are 10+2+1 and 10+3 and so intersect by element 10.
Have you tried running it? It gives 1 for your example
My example is [10, 3, 2, 1], read carefully. And the answer is 2, as expected, which is wrong.
Btw, you didn't even edit code for + = 1 instead of + = Array[Num]. I did in the link above.
It seems to produce correct answer when the array is sorted.
Of course, because in this order you proceed instersecting element as last. You can try [1, 10, 20, 30] and sum of 31 (should get 2 also: 1+10+20 and 1+30), if you really think, that sorting changes anything. But better try to understand what I want to say and why it's not working on this examples.
I see now. You are right. My approach is wrong.
Hint: try to find all pairs (x, y) such that you can find two non-intersecting subsets with sums x and y. It's very similar to all possible sums of subsets.
O(N·totalsum) solution. Let's count dp[n][diff] — maximum such X, that in elements S[1], ... S[n] there are two non-intersecting subsets with sums X and X + diff. Calculation is simple, n'th element can either be in the first subset, in second or not used at all. And problem's answer is dp[N][0]
Could you please also provide the equation for calculating dp[n][diff] for better understanding?
Let mark S[n] (current element) as just S. Than dp[n][diff] = max(dp[n - 1][diff], dp[n - 1][diff + S] + S, dp[n - 1][diff - S]). This three choises in max correspond to not used current element at all, add to the first subset and add to the second one.
Thanks
Exactly how did you initialized dp[][] ? I don't understand your idea clearly, regarding Relationship between max function's arguments and taking/not taking element in subset. And when diff ==0 Diff-S <0 so there might be IndexError.
You can always add an offset to all values in the second dimension in these cases. Make 0 equal to offset, then you need to subtract offset from second value to get actual difference.
For anyone who wants to test their code: URI 1700
This problem can also be tested here https://leetcode.com/problems/tallest-billboard/