I want to know how 3 partition problem is NP complete ? We have to find triplets in set which sums to target. So isn't time complexity will be O(n^3) which is polynomial ?
solution: https://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value
original question: https://en.wikipedia.org/wiki/3-partition_problem
Also, can someone explain the reduction from partition to 3 partition by example.
The problem is not to find a triplet (which would be O(n^3)) but a way to split the set into triplets which all have the same sum; the brute-force approach would be to test all such partitions, which would not be polynomial.