Given an array and a sum, find the count of unique subsets with each subset’s sum equal to the given sum value.
Examples:
Input : 4 12 5 9 12 9 Output : 2 (subsets will be [4, 5] and [9]) Input : 1 2 3 4 5 10 Output : 3
We will use dynamic programming to solve this problem and this solution has time complexity of O(n2). Below is dp[][] used in the code –
_ | 4 12 5 9 12 0 |[1, 1, 1, 1, 1] 1 |[0, 0, 0, 0, 0] 2 |[0, 0, 0, 0, 0] 3 |[0, 0, 0, 0, 0] 4 |[1, 1, 1, 1, 1] 5 |[0, 0, 1, 1, 1] 6 |[0, 0, 0, 0, 0] 7 |[0, 0, 0, 0, 0] 8 |[0, 0, 0, 0, 0] 9 |[0, 0, 1, 2, 2]
Below is the Python Code :
# Python code to find the number of unique subsets # with given sum in the given array def help(a,s): dp = [[0 for i in range(len(a))] for j in range(0,s+1)] for i in range(len(a)): dp[0][i] = 1 for i in range(1,s+1): if i == a[0]: dp[i][0] = 1 for i in range(1, s+1): for j in range(1, len(a)): if a[j]<=i: dp[i][j] = dp[i][j-1] + dp[i-a[j]][j-1] else: dp[i][j] = dp[i][j-1] return dp[s][len(a)-1] # driver code a = [4, 12, 5, 9, 12] s = 9 print(help(a,s)) |
Output :
2
