Write a method named partitionable that uses dynamic programming to discover whether an array can be partitioned into two sub-lists of equal sum.
Your method should accept an array of integers as a parameter, and return true if the given list can be partitioned equally, and false if not.
For example, the array {1, 2, 3} can be split into {1, 2} and {3}, both of which have a sum of 3.
The array {1, 2, 3, 4, 6} can be split into {1, 3, 4} and {2, 6}, both of which have a sum of 8.
For the array {2, 1, 8, 3}, there is no way to split the array into two sub-arrays whose sum is equal.
The table below indicates various possible contents for a array, and the value that would be returned by the call of your method:
| Array Contents |
Value Returned |
Reasoning |
{1, 2, 3, 4, 6} |
true |
{1, 3, 4} and {2, 6} |
{1, 2, 3} |
true |
{1, 2} and {3} |
{2, 1, 8, 3} |
false |
|
{8, 8} |
true |
{8} and {8} |
{42} |
false |
|
{} |
true |
{} and {} |
The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach.
Do not use recursion. Your solution must use dynamic programming instead.
You are allowed to construct any data structures (array, list, set, map, etc.) necessary to store the data for your dynamic programming algorithm.
You may assume that none of the values in the array are negative.
