Coursera DSA Algorithmic toolbox week 4 2nd question- Partitioning Souvenirs

Question

Problem Statement- You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought.

Problem Description Input Format- The first line contains an integer ... The second line contains integers v1, v2, . . . ,vn separated by spaces.

Constraints- 1 . .. . 20, 1 . .... . 30 for all ...

Output Format- Output 1, if it possible to partition 𝑣1, 𝑣2, . . . , 𝑣𝑛 into three subsets with equal sums, and 0 otherwise.

What's Wrong with this solution? I am getting wrong answer when I submit(#12/75) I am solving it using Knapsack without repetition taking SUm/3 as my Weight. I back track my solution to replace them with 0. Test cases run correctly on my PC. Although I did it using OR logic, taking a boolean array but IDK whats wrong with this one??

Example- 11

17 59 34 57 17 23 67 1 18 2 59

(67 34 17)are replaced with 0s. So that they dont interfare in the next sum of elements (18 1 23 17 59). Coz both of them equal to 118(sum/3) Print 1.

#include <iostream>
#include <vector>

using namespace std;
int partition3(vector<int> &w, int W)
{
        int N = w.size();

//using DP to find out the sum/3 that acts as the Weight for a Knapsack problem
        vector<vector<int>> arr(N + 1, vector<int>(W + 1));
        for (int k = 0; k <= 1; k++)
        {
//This loop runs twice coz if 2x I get sum/3 then that ensures that left elements will make up sum/3 too
                for (int i = 0; i < N + 1; i++)
                {
                        for (int j = 0; j < W + 1; j++)
                        {
                                if (i == 0 || j == 0)
                                        arr[i][j] = 0;
                                else if (w[i - 1] <= j)
                                {
                                        arr[i][j] = ((arr[i - 1][j] > (arr[i - 1][j - w[i - 1]] + w[i - 1])) ? arr[i - 1][j] : (arr[i - 1][j - w[i - 1]] + w[i - 1]));
                                }
                                else
                                {
                                        arr[i][j] = arr[i - 1][j];
                                }
                        }
                }

                if (arr[N][W] != W)
                        return 0;
                else
                {
//backtrack the elements that make the sum/3 and = them to 0 so that they don't contribute to the next //elements that make sum/3
                        int res = arr[N][W];
                        int wt = W;
                        for (int i = N; i > 0 && res > 0; i--)
                        {
                                if (res == arr[i - 1][wt])
                                        continue;
                                else
                                {
                                        std::cout << w[i - 1] << " ";
                                        res = res - w[i - 1];
                                        wt = wt - w[i - 1];
                                        w[i - 1] = 0;
                                }
                        }
                }
        }
        if (arr[N][W] == W)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

int main()
{
        int n;
        std::cin >> n;
        vector<int> A(n);
        int sum = 0;
        for (size_t i = 0; i < A.size(); ++i)
        {
                int k;
                std::cin >> k;
                A[i] = k;
                sum += k;
        }
        if (sum % 3 == 0)
                std::cout << partition3(A, sum / 3) << '\n';
        else
                std::cout << 0;
}

Answer 1

Sum/3 can be achieved by multiple ways!!!! So backtracking might remove a subset that has an element that should have been a part of some other subset 8 1 6 is 15 as well as 8 2 5 makes 15 so better is u check this

if(partition3(A, sum / 3) == sum / 3 && partition3(A, 2 * (sum / 3)) == 2 * sum / 3 && sum == partition3(A, sum))