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
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/python-find-the-number-of-unique-subsets-with-given-sum-in-array/ […]