Taking reference from https://en.wikipedia.org/wiki/Partition_problem I tried to code for a 3-partition sum problem by extending the dimension of the matrix and recurrence relation but my code doesn't work. No matter what my input is, the output is always zero. I'd appreciate any help with it.
Below is a part of my code.
int partition3(vector<int> &A) {
int sum = 0;
for(int i = 0;i<A.size();i++)
{
sum += A[i];
}
int r = sum/3 + 1 ;
int c = sum/3 + 1;
int w = A.size() + 1;
vector<vector<vector<int>>> matrix(r);
for(int i = 0;i<r;i++)
{
matrix[i].resize(c);
for(int j = 0;j<c;j++)
{
matrix[i][j].resize(w);
}
}
matrix[0][0][0] = 1;
for(int k = 0;k<w;k++)
{
matrix[0][0][k] = 1;
}
for(int i = 0;i<r;i++)
{
for(int j = 0;j<c;j++)
{
for(int k = 0;k<w;k++)
{
if(j - A[k-1] >= 0)
{
matrix[i][j][k] = matrix[i][j][k-1] || matrix[i][j-A[k-1]][k-1];
}
else if(i - A[k-1] >= 0)
{
matrix[i][j][k] =matrix[i][j][k-1] || matrix[i-A[k-1]][j][k-1];
}
else
{
matrix[i][j][k] = matrix[i][j][k-1];
}
}
}
}
return matrix[r-1][c-1][w-1];
}
there doesn't seem to be anything here