Dynamic Programming Questions Medium
To solve the Partition Equal Subset Sum problem using Dynamic Programming, we can follow the below steps:
1. First, we need to check if the sum of all elements in the given array is even. If it is not, then it is not possible to divide the array into two subsets with equal sums, so we return false.
2. If the sum is even, we create a 2D boolean array dp of size (n+1) x (sum/2 + 1), where n is the number of elements in the array and sum is the total sum of all elements divided by 2.
3. Initialize the first column of dp as true, as we can always form a subset with sum 0 by not selecting any element.
4. Iterate through the array elements from 1 to n and for each element, iterate through the possible sum values from 1 to sum/2.
5. For each element, if the current element is greater than the current sum value, then we copy the value from the previous row for the same sum value.
6. If the current element is less than or equal to the current sum value, then we check if either including the current element or excluding it can form a subset with the current sum value. If either of them is true, we mark dp[i][j] as true.
7. Finally, we return the value of dp[n][sum/2]. If it is true, it means we can divide the array into two subsets with equal sums, otherwise, it is not possible.
The time complexity of this approach is O(n*sum), where n is the number of elements in the array and sum is the total sum of all elements. The space complexity is O(n*sum) as well, due to the 2D dp array.