Given an array of non-negative integers, check whether there are two equals sum subset exist.
Let isSubsetSum(int array, int n, int sum) is a recursive function which is used to check whether there are two subsets with the sum equal to sum.
isSubsetSum(array, n, sum) = true, if sum == 0
isSubsetSum(array, n, sum) = false, if sum > 0 and n == 0.
Worst case time complexity of the above solution is exponential.
Dynamic programming approach
We can solve the problem in Pseudo-polynomial time. We create a 2D array ‘dp’ and the value of dp[i][j] will be true if there is a subset of array[0..j-1] with the sum equal to j, otherwise false. Finally, we will return dp[sum][n].