priyesh001's blog

Two subsets with maximum equal sum
By priyesh001, 7 years ago, In English

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?

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide the link for that problem?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks giorgosgiapis, that solution looks correct and easy to understand.

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Have you tried running it? It gives 1 for your example

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              It seems to produce correct answer when the array is sorted.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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]

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please also provide the equation for calculating dp[n][diff] for better understanding?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For anyone who wants to test their code: URI 1700

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This problem can also be tested here https://leetcode.com/problems/tallest-billboard/

→ Reply