0
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ Can you detail what you mean by "backtrack those numbers"? $\endgroup$ – Simon Jan 30 at 20:59
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 30 at 22:51
1
$\begingroup$

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.
$\endgroup$
2
  • 1
    $\begingroup$ thanks, but that wasn't my question: I want to know whether my solution is correct $\endgroup$ – CNNTT Jan 30 at 20:52
  • $\begingroup$ I updated the answer with details why I think the original solution can't work in some cases. $\endgroup$ – Simon Jan 30 at 21:07
-1
$\begingroup$

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];
    }
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Feb 2 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.