How to split a set into three subsets with the same sum of elements?

Question

Programming

Good afternoon.
I came across a task from the section on dynamic programming, which causes me difficulties. It is necessary to construct an algorithm that, given a set, determines whether it can be divided into three parts, in which the sums of all elements will be equal. For example:
[1, 2, 3, 4, 4, 5, 8] -> {1,8}, {4,5}, {2,3,4}
Obviously, if the sum of all elements is not divisible by 3, then the set does not contain such a partition (the simplest part:) ). But how to proceed? It seems like we have to check which subset our a_i element belongs to.
But it is impossible to formalize all this and fasten the dynamics.
I would appreciate it if you could point me in the right direction.

Answer 1

The knapsack problem, even two ones :)
Create an array M[0..S/3,0..S/3] (you can use a bit array, but a larger one is better - to store back references). Elements M[a,b] will be marked in it, such that it is possible to select disjoint subsets with sums a and b from the already scanned elements of the current set.
When the next element x arrives, do M[a,b]=M[a,b] | M[ax, b] | M[a,bx] for all a,b starting from the end (from large a,b). If at the same time 0 changed to 1 - mark in the array of back links from which element you got here.
Complexity - O(n*S^2). Can it be done better, I don't know.
Here is a variant of the code - but it only prints two sets. How to print the third, figure it out.

spoiler

static void Main(string[] args) {
            int[] dat=Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
            int S=0;
            foreach(int x in dat) S+=x;
            if(S%3!=0) {
                Console.WriteLine("-1"); return;
            }
            S/=3;
            int[,] M=new int[S+1,S+1];
            M[0,0]=-1;
            foreach(int x in dat) {
                for(int a=S;a>=0;a--) {
                    for(int b=S;b>=0;b--) {
                        if(M[a,b]==0) {
                            if(a>=x && M[a-x,b]!=0) M[a,b]=x;  // back by set1
                            else if(b>=x && M[a,b-x]!=0) M[a,b]=-x;  // back by set2
                        }
                    }
                }
            }
            if(M[S,S]==0) {
                Console.WriteLine("-1"); return;
            }
            int u=S,v=S;
            string res1="",res2="";
            while(u!=0 || v!=0) {
                if(M[u,v]>0) {
                    res1+=" "+M[u,v]; u-=M[u,v];
                } else {
                    res2+=" "+(-M[u,v]); v+=M[u,v];
                }
            }
            Console.WriteLine(res1);
            Console.WriteLine(res2);
        }

Answer 2

Read carefully about splits . Why be smart.

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

#x = [1, 2, 3, 4, 4, 5, 8]
#x = [5, 7, 12, 3, 3, 1, 5]
x = [123, 1, 8, 4, 120, 59, 59, 10]

if (sum(x) % 3 == 0):
  tmp = sum(x) / 3
  x.sort()
  x.reverse()
  for i in range(3):
    y = []
    j = 0
    while (sum(y) != tmp):
      if ((sum(y) + x[j]) <= tmp):
        y.append(x[j])
        del(x[j])
      else:
        j += 1
    print(y)
else:
  print('Вознеможно разбить на 3 равные части!')

Answer 3

But how to proceed?

Some kind of recursive algorithm, where:
1. we collect elements up to the sum S / 3 in the 1st set ...
2. for each found combination of item 1, we collect elements up to the sum S / 3 in the 2nd set ...
3 See if the sum of what's left is S/3?
Search tree.
No matter how smart you are, the final decision will be a variant of this.
You can come up with some greedy algorithms so as not to immediately go deep into recursion to the full depth.
A good task ...
But cumbersome, so I don't put it here.
Here is a solution: examples of tasks when learning C ++

$ ./3set
Вводите числа построчно (пустая строка - конец ввода):
1 2 3 4
4 5 8

{ 1, 2, 3, 4, 4, 5, 8 } ->
{ 1, 8 }
{ 4, 5 }
{ 2, 3, 4 }

Answer 4

Decided as best I could

function summ(a){
 if(a.length==0){return 0}
 else{res = 0; for(var i=0;i<a.length;i++){res=res+a[i]} return res;}
}
 var ar = [5, 7, 12, 3, 3, 1, 5]; 
ar=ar.sort(function(a, b){return a-b}); 
var b=[];
var c =[];
 var d=[]; 
for(var i=ar.length-1;i>-1;i--){
if(summ(b)+ar[i]<=summ(ar)/3) {b.push(ar[i])}
else if(summ(c)+ar[i]<=summ(ar)/3) {c.push(ar[i])}
else if(summ(d)+ar[i]<=summ(ar)/3) {d.push(ar[i])}}; 
console.log(b);console.log(c);console.log(d)

Even it seems to me that it will not always work)