Determine if there is a 3-partition given n numbers using Dynamic Programming

Question

I found a solution to the 3-partition problem, that is, given n numbers, you determine if you can form three (disjoin) subsets such that all are equal (that is, each subset has a sum equal to the sum of the n numbers/3).

A similar question is at: 3-PARTITION problem. However, I am looking for an explanation of the below code.

Simply put, I have no idea what is going on. I don't know what T is, what i or j are, what k is, or why we k and j start at N and are being decremented, what "T[j + C[i]][k] = true; T[j][k + C[i]] = true" means, or why are we returning T[N/3]?

bool T[10240][10000];
bool partition( vector< int > C ) {
    // compute the total sum
    int n = C.size();
    int N = 0;

    for( int i = 0; i < n; i++ ) N += C[i];
    // initialize the table
    T[0][0] = true;
        memset(T, 0, 10000^2);

    // process the numbers one by one
    for( int i = 0; i < n; i++ ) {
                for (int j = N; j >= 0; --j) {
                        for (int k = N; k >= 0; --k) {
                                if (T[j][k]) {
                                        T[j + C[i]][k] = true;
                                        T[j][k + C[i]] = true;
                                }
                        }
                }
        }
    return T[N / 3];
}

score 4 · Answer 1 · answered Mar 26 '13 at 08:58

First of all, the return value should be T[N / 3][N / 3].

T[i][j] means whether it is possible to get the first partition which sums up to i and the second partition which sums up to j. Obviously, since the sum of all n numbers is N. So T[i][j] is true means the array can be divided into three partitions with sums are i, j and N-i-j respectively.

Initially, T[0][0] is true and all others are false, which means at the very beginning, it is only possible to divide the numbers into three partitions: 0, 0 and N. The for loop of i iterates all n numbers, and each time, the number C[i] can either be grouped to the first partition or the second. That's why set T[j+C[i]][k] and T[j][k+C[i]] to be true.

The reason why variables j and k start from N and be decremented is, to avoid counting a single number more than once. Consider in this way: if, for example, j starts from 0 to N, then T[j][k], T[j+C[i]][k], T[j+C[i]*2][k], ... , T[j+C[i]*x][k] will all be set true, which is incorrect. You can simply pick a small case to try simulating the process yourself.

score 1 · Answer 2 · answered May 03 '20 at 07:00

Correct C++ implementation for this would look like this:

int partition3(vector<int> &A)
{
  int sum = accumulate(A.begin(), A.end(), 0);
  if (sum % 3 != 0)
  {
    return false;
  }
  int size = A.size();

  vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, 0));
  dp[0][0] = true;

  // process the numbers one by one
  for (int i = 0; i < size; i++)
  {
    for (int j = sum; j >= 0; --j)
    {
        for (int k = sum; k >= 0; --k)
        {
            if (dp[j][k])
            {
                dp[j + A[i]][k] = true;
                dp[j][k + A[i]] = true;
            }
        }
    }
  }
  return dp[sum / 3][sum / 3];
}

Determine if there is a 3-partition given n numbers using Dynamic Programming

2 Answers2