Write a function named partitionable
that uses dynamic programming to discover whether a vector can be partitioned into two sublists of equal sum.
Your function should accept a reference to vector of integers as a parameter, and return true
if the given list can be partitioned equally, and false
if not.
For example, the vector {1, 2, 3}
can be split into {1, 2}
and {3}
, both of which have a sum of 3.
The vector {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 vector {2, 1, 8, 3}
, there is no way to split the vector into two subvectors whose sum is equal.
The table below indicates various possible contents for a vector, and the value that would be returned by the call of your function:
Vector 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 bottomup dynamic programming approach.
Do not use recursion. Your solution must use dynamic programming instead.
You are allowed to construct any data structures (array, vector, set, map, etc.) necessary to store the data for your dynamic programming algorithm.
You may assume that none of the values in the vector are negative.