3-Same-Sum-Subsets

Question

Hey Coders,

I'm currently trying to solve the following problem with dynamic programming! Here is the problem:

Given a set S of positive integers.
Are there 3 subsets (S1,S2,S3), such that:
1) sum (S1) = sum (S2) = sum (S3)
2) S1,S2,S3 aren't empty
3) sum (S) = sum (S1) + sum (S2) + sum (S3)

EXAMPLE 1:
input: S = [4,7,5,2,9]
output: True

( one possible combination: S1 = [4,5] S2 = [7,2] S3 = [9] )

Example 2:
input: [3,2,2,1]
output: False

I've no idea how to solve it. all hints are helpful!

Answer 1

in dynamic programming you have first to find a recursive algorithm before optimizing it using some data struct! my answer was just to provide you some tip.

furthermore the set of all subset of S consists of 2^|S| elements, for example for {1,2} you have {empty} {1} {2} and {1,2} 2^2=4 subsets (you can also prove this by induction).

Answer 2

after some research on the problem, I wrote this (pseudo) polynomial algorithm. check it out!!!
https://code.sololearn.com/cY62tyXKxlv3/?ref=app

Answer 3

i would start finding all the 2^|S| subsets of set S, and calculating sum(Si) of each subset Si

Answer 4

That's the 'brute force' way and it leads to very inefficient runtime!

I'm looking for a way to create S1,S2,S3 by adding a new element to it. And if the new sum of the increased set is larger than a threshold, i need to do some backtracking (placing the new element in a different Set)!

But i don't know how to do the backtraking!

By the way: It should be 3^|S| subsets!

Answer 5

you have to find a minimal subset Si with sum(Si)=sum(S)\3 and continue on the remaining elements on S