# Question concerning subset sum problem: split into 3 equal subsets

Task: Given an array $$arr[a_1, a_2, \dots, a_n]$$ of integers, let $$A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$$. Determine whether it is possible to spit $$arr[]$$ into 3 subsequences of equal sum, i.e. if $$s_1 =s_2 = s_3 =\dfrac{A}{3}$$ where $$s_1 ,s_2 , s_3$$ denoted the splitted arrays.

My thoughts: I will first examine whether there exists some sequence of numbers that sums up to $$\dfrac{A}{3}$$ via dp, then I will backtrack those numbers, "throw them out" (meaning I won't consider them anymore), and proceed with the remaining numbers of the array. After doing this a second time I examine whether the numbers left sum up to $$\dfrac{A}{3}$$ and return true if this is the case. Even though this sounds valid to me I somehow doubt the correctness of this.

Recurrence of DP: $$dp[i][j] = dp[i-1][j-a_j] \text{ OR } dp[i-1][j]$$

$$dp[]$$ is a boolean array of dimension $$n \times\dfrac{A}{3}$$.

• Can you detail what you mean by "backtrack those numbers"? – Simon Jan 30 at 20:59
• I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question. We discourage "please check whether my answer is correct" questions, as such are unlikely to be useful to anyone else in the future. – D.W. Jan 30 at 22:51

I don't think the proposed algorithm is correct. It may happen that the first solve for $$A/3$$ picks a set of numbers that makes it impossible to split the remainder into equal halves. Consider this example:

• Given the set of numbers $$\{1,1,3,3,3,4,8,10\}$$, which sum to $$A=3*11$$
• Assume that the first DP picks $$||\{1,1,3,3,3\}||_1=11$$
• It is impossible to split the remaining set $$\{4,8,10\}$$ into equal halves.

Here's a recursive function in pseudocode instead which computes what you need in a single step:

bool CanBuild3EqualSums(int sumA, int sumB, int sumC, int[] numbers)
{
if(numbers is empty)
return sumA == sumB && sumB == sumC;
else
return CanBuild3EqualSums(sumA + numbers[0], sumB, sumC, numbers.WithoutFirst())
|| CanBuild3EqualSums(sumA, sumB + numbers[0], sumC, numbers.WithoutFirst())
|| CanBuild3EqualSums(sumA, sumB, sumC + numbers[0], numbers.WithoutFirst())
}


This is a pure function (without side-effects). Add memoization and you'll end up with a DP algorithm. Of course, there are many other ways to formulate this. There is some potential for a more efficient, practical implementation:

• You could pass the index of the next number, instead of the whole array.
• You could get rid of sumC, and compute when needed, based on sumA and sumB
• If you have small values, a bottom-up formulation might be more efficient.
• thanks, but that wasn't my question: I want to know whether my solution is correct – CNNTT Jan 30 at 20:52
• I updated the answer with details why I think the original solution can't work in some cases. – Simon Jan 30 at 21:07

Here my solution:

    boolean 3_Partition(int arr[]) {
if (arr == null)
return false;
int sum = Arrays.stream(arr).sum();
if (sum % 3 != 0)
return false;
int n = arr.length;
boolean dp[][][] = new boolean[n+1][sum = sum / 3 + 1][sum];
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < sum; j++) {
for (int k = 0; k < sum; k++) {
if (i == 0 ) dp[i][j][k] = false;
else if (j == 0) dp[i][j][k] = true;
else if (k == 0) dp[i][j][k] = true;
else  dp[i][j][k] = j >= arr[i-1] && k >= arr[i-1] ? dp[i - 1][j - arr[i-1]][k] || dp[i - 1][j][k - arr[i-1]] || dp[i - 1][j][k]
: j >= arr[i-1] ? dp[i - 1][j - arr[i-1]][k] || dp[i - 1][j][k]
: k >= arr[i-1] ? dp[i - 1][j][k - arr[i-1]] || dp[i - 1][j][k] : dp[i - 1][j][k];
}
}
}
return dp[n][sum-1][sum-1];
}

• We discourage code-only answers. We're not a coding site; we're looking for answers that come with explanation, justification, concise pseudocode, and/or proofs of correctness. You said elsewhere that your question was whether the approach outlined in the post is correct, but this doesn't appear to answer that question. – D.W. Feb 2 at 0:23