# Fully documented C++ DP Solution (22ms)

• I spent lot of time reading other answers and explanations from other sites and struggled to really get the DP solution. I think I finally got it and wanted to document my understanding in the comments. Other than the basic algorithm I have not spent time in optimizing the time. It runs at 22ms. I am using the 1-D DP method. It runs in O(nk) time and O(nk) space. n=array size, k=sum of all elements

``````class Solution {
public:

bool subset_sum(const vector<int>& a, int target)
{
/* subset_sum problem is NP-Complete. So, basic recursive solution
would be exponential time. We can solve this with dynamic programming
in O(nk) time (n=array size, k=target) using O(k) space.

each index in dp[] array corresponds to a sum value. dp[s] is true
if sum s can be obtained from the subset of this array.

if we are looking at an element of the array x, dp[s] can be set to
true of dp[s-x] is true. This is because if sum (s-x) is possible then
adding x to that sum will get us to sum s. Finally, building up this
dp array can give us the final answer at dp[target] */

vector<bool> dp(target + 1);

/* dp[0] is true, as we can always get sum of 0 using an empty set */
dp[0] = true;

/* for each element in array, update the dp array */
for (int x : a) {

/* iterating from right to left in dp array, as we are going to
refer to smaller (s-x) index when updating index s. We dont want
dp[s-x] updated before dp[s] */
for (int s = target; s > 0; s--) {
if (s >= x && dp[s - x] == true) {
dp[s] = true;
/* if target sum is found, we can return immediately */
if (s == target) {
return true;
}
}
}
}
/* if target sum is never set to true, we will reach here */
return false;
}

bool canPartition(vector<int>& nums)
{
/* find sum of all elements in array */
int sum = 0;
for (int x : nums) {
sum += x;
}
/* we can partition the array into two equal values, only if total sum
of the elements is even. So, return false if sum is odd */
if (sum % 2 != 0) {
return false;
}

/* now, the problem becomes more clear. We need to check if there is a
subset of elements in the array whose total is sum/2. This is a well
known subset sum problem */
return subset_sum(nums, sum/2);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.