3-PARTITION problem

by

It’s easy to generalize 2-sets solution for 3-sets case.

In original version, you create array of boolean sums where sums[i] tells whether sum i can be reached with numbers from the set, or not. Then, once array is created, you just see if sums[TOTAL/2] is true or not.

Since you said you know old version already, I’ll describe only difference between them.

In 3-partition case, you keep array of boolean sums, where sums[i][j] tells whether first set can have sum i and second – sum j. Then, once array is created, you just see if sums[TOTAL/3][TOTAL/3] is true or not.

If original complexity is O(TOTAL*n), here it’s O(TOTAL^2*n).
It may not be polynomial in the strictest sense of the word, but then original version isn’t strictly polynomial too 🙂

More Related Contents:

  1. How to determine the longest increasing subsequence using dynamic programming?
  2. Subset Sum algorithm
  3. What is dynamic programming? [closed]
  4. Getting the submatrix with maximum sum?
  5. Box stacking problem
  6. how to find longest palindromic subsequence?
  7. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  8. How to count integers between large A and B with a certain property?
  9. How to understand the dynamic programming solution in linear partitioning?
  10. Maximum Contiguous Subsequence Sum of At Least Length L
  11. Algorithm to beat Strassen’s Algorithm
  12. What does O(log n) mean exactly?
  13. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  14. Generate an integer that is not among four billion given ones
  15. Find duplicates in an array, without using any extra space
  16. How to generate Sudoku boards with unique solutions
  17. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  18. Maximize the rectangular area under Histogram
  19. Efficient algorithm for ordering different types of objects
  20. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  21. How to find two most distant points?
  22. Smooth spectrum for Mandelbrot Set rendering
  23. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  24. Sorting an array with minimal number of comparisons
  25. Determining if two line segments intersect? [duplicate]
  26. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  27. Non-Recursive Merge Sort
  28. Reversing CRC32
  29. The intersection of all combinations of n sets
  30. Binary tree level order traversal

Leave a Comment