Python | Find the number of unique subsets with given sum in array

0 0 1 minute read

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(n²). 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)) 