# Subset Sum Problem | DP-25

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:

```Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.
```

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.

Following is the recursive formula for isSubsetSum() problem.

```isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0
``` Following is naive recursive implementation that simply follows the recursive structure mentioned above.

div class="responsive-tabs">

## C++

 `// A recursive solution for subset sum problem ` `#include ` ` `  `// Returns true if there is a subset of set[] with sun equal to given sum ` `bool` `isSubsetSum(``int` `set[], ``int` `n, ``int` `sum) ` `{ ` `   ``// Base Cases ` `   ``if` `(sum == 0) ` `     ``return` `true``; ` `   ``if` `(n == 0 && sum != 0) ` `     ``return` `false``; ` ` `  `   ``// If last element is greater than sum, then ignore it ` `   ``if` `(set[n-1] > sum) ` `     ``return` `isSubsetSum(set, n-1, sum); ` ` `  `   ``/* else, check if sum can be obtained by any of the following ` `      ``(a) including the last element ` `      ``(b) excluding the last element   */` `   ``return` `isSubsetSum(set, n-1, sum) ||  ` `                        ``isSubsetSum(set, n-1, sum-set[n-1]); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `  ``int` `set[] = {3, 34, 4, 12, 5, 2}; ` `  ``int` `sum = 9; ` `  ``int` `n = ``sizeof``(set)/``sizeof``(set); ` `  ``if` `(isSubsetSum(set, n, sum) == ``true``) ` `     ``printf``(``"Found a subset with given sum"``); ` `  ``else` `     ``printf``(``"No subset with given sum"``); ` `  ``return` `0; ` `} `

## Java

 `// A recursive solution for subset sum ` `// problem ` `class` `GFG { ` `     `  `    ``// Returns true if there is a subset ` `    ``// of set[] with sum equal to given sum ` `    ``static` `boolean` `isSubsetSum(``int` `set[], ` `                            ``int` `n, ``int` `sum) ` `    ``{ ` `        ``// Base Cases ` `        ``if` `(sum == ``0``) ` `            ``return` `true``; ` `        ``if` `(n == ``0` `&& sum != ``0``) ` `            ``return` `false``; ` `         `  `        ``// If last element is greater than  ` `        ``// sum, then ignore it ` `        ``if` `(set[n-``1``] > sum) ` `            ``return` `isSubsetSum(set, n-``1``, sum); ` `         `  `        ``/* else, check if sum can be obtained  ` `        ``by any of the following ` `            ``(a) including the last element ` `            ``(b) excluding the last element */` `        ``return` `isSubsetSum(set, n-``1``, sum) ||  ` `            ``isSubsetSum(set, n-``1``, sum-set[n-``1``]); ` `    ``} ` `     `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main (String args[]) ` `    ``{ ` `        ``int` `set[] = {``3``, ``34``, ``4``, ``12``, ``5``, ``2``}; ` `        ``int` `sum = ``9``; ` `        ``int` `n = set.length; ` `        ``if` `(isSubsetSum(set, n, sum) == ``true``) ` `            ``System.out.println(``"Found a subset"` `                          ``+ ``" with given sum"``); ` `        ``else` `            ``System.out.println(``"No subset with"` `                               ``+ ``" given sum"``); ` `    ``} ` `} ` ` `  `/* This code is contributed by Rajat Mishra */`

## Python3

 `# A recursive solution for subset sum ` `# problem ` ` `  `# Returns true if there is a subset  ` `# of set[] with sun equal to given sum ` `def` `isSubsetSum(``set``,n, ``sum``) : ` `   `  `    ``# Base Cases ` `    ``if` `(``sum` `=``=` `0``) : ` `        ``return` `True` `    ``if` `(n ``=``=` `0` `and` `sum` `!``=` `0``) : ` `        ``return` `False` `  `  `    ``# If last element is greater than ` `    ``# sum, then ignore it ` `    ``if` `(``set``[n ``-` `1``] > ``sum``) : ` `        ``return` `isSubsetSum(``set``, n ``-` `1``, ``sum``); ` `  `  `    ``# else, check if sum can be obtained ` `    ``# by any of the following ` `    ``# (a) including the last element ` `    ``# (b) excluding the last element    ` `    ``return` `isSubsetSum(``set``, n``-``1``, ``sum``) ``or` `isSubsetSum(``set``, n``-``1``, ``sum``-``set``[n``-``1``]) ` `     `  `     `  `# Driver program to test above function ` `set` `=` `[``3``, ``34``, ``4``, ``12``, ``5``, ``2``] ` `sum` `=` `9` `n ``=` `len``(``set``) ` `if` `(isSubsetSum(``set``, n, ``sum``) ``=``=` `True``) : ` `    ``print``(``"Found a subset with given sum"``) ` `else` `: ` `    ``print``(``"No subset with given sum"``) ` `     `  `# This code is contributed by Nikita Tiwari. `

## C#

 `// A recursive solution for subset sum problem ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Returns true if there is a subset of set[] with sum ` `    ``// equal to given sum ` `    ``static` `bool` `isSubsetSum(``int` `[]``set``, ``int` `n, ``int` `sum) ` `    ``{ ` `        ``// Base Cases ` `        ``if` `(sum == 0) ` `            ``return` `true``; ` `        ``if` `(n == 0 && sum != 0) ` `            ``return` `false``; ` `         `  `        ``// If last element is greater than sum,  ` `        ``// then ignore it ` `        ``if` `(``set``[n-1] > sum) ` `            ``return` `isSubsetSum(``set``, n-1, sum); ` `         `  `        ``/* else, check if sum can be obtained  ` `        ``by any of the following ` `        ``(a) including the last element ` `        ``(b) excluding the last element */` `        ``return` `isSubsetSum(``set``, n-1, sum) ||  ` `                       ``isSubsetSum(``set``, n-1, sum-``set``[n-1]); ` `    ``} ` `     `  `    ``// Driver program  ` `    ``public` `static` `void` `Main () ` `    ``{ ` `        ``int` `[]``set` `= {3, 34, 4, 12, 5, 2}; ` `        ``int` `sum = 9; ` `        ``int` `n = ``set``.Length; ` `        ``if` `(isSubsetSum(``set``, n, sum) == ``true``) ` `            ``Console.WriteLine(``"Found a subset with given sum"``); ` `        ``else` `            ``Console.WriteLine(``"No subset with given sum"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` ``\$sum``) ` `        ``return` `isSubsetSum(``\$set``, ``\$n` `- 1, ``\$sum``); ` `     `  `    ``/* else, check if sum can be  ` `       ``obtained by any of the following ` `        ``(a) including the last element ` `        ``(b) excluding the last element */` `    ``return` `isSubsetSum(``\$set``, ``\$n` `- 1, ``\$sum``) ||  ` `        ``isSubsetSum(``\$set``, ``\$n` `- 1,  ` `                    ``\$sum` `- ``\$set``[``\$n` `- 1]); ` `} ` ` `  `// Driver Code ` `\$set` `= ``array``(3, 34, 4, 12, 5, 2); ` `\$sum` `= 9; ` `\$n` `= 6; ` ` `  `if` `(isSubsetSum(``\$set``, ``\$n``, ``\$sum``) == true) ` `    ``echo``"Found a subset with given sum"``; ` `else` `    ``echo` `"No subset with given sum"``; ` `     `  `// This code is contributed by Anuj_67  ` `?> `

Output:

```Found a subset with given sum
```

The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).

We can solve the problem in Pseudo-polynomial time using Dynamic programming. We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]

## C++

 `// A Dynamic Programming solution for subset sum problem ` `#include ` `  `  `// Returns true if there is a subset of set[] with sun equal to given sum ` `bool` `isSubsetSum(``int` `set[], ``int` `n, ``int` `sum) ` `{ ` `    ``// The value of subset[i][j] will be true if there is a  ` `    ``// subset of set[0..j-1] with sum equal to i ` `    ``bool` `subset[n+1][sum+1]; ` `  `  `    ``// If sum is 0, then answer is true ` `    ``for` `(``int` `i = 0; i <= n; i++) ` `      ``subset[i] = ``true``; ` `  `  `    ``// If sum is not 0 and set is empty, then answer is false ` `    ``for` `(``int` `i = 1; i <= sum; i++) ` `      ``subset[i] = ``false``; ` `  `  `     ``// Fill the subset table in botton up manner ` `     ``for` `(``int` `i = 1; i <= n; i++) ` `     ``{ ` `       ``for` `(``int` `j = 1; j <= sum; j++) ` `       ``{ ` `         ``if``(j= set[i-1]) ` `           ``subset[i][j] = subset[i-1][j] ||  ` `                                 ``subset[i - 1][j-set[i-1]]; ` `       ``} ` `     ``} ` `  `  `     ``/*   // uncomment this code to print table ` `     ``for (int i = 0; i <= n; i++) ` `     ``{ ` `       ``for (int j = 0; j <= sum; j++) ` `          ``printf ("%4d", subset[i][j]); ` `       ````printf(" "); ``` `     ``}*/` `  `  `     ``return` `subset[n][sum]; ` `} ` `  `  `// Driver program to test above function ` `int` `main() ` `{ ` `  ``int` `set[] = {3, 34, 4, 12, 5, 2}; ` `  ``int` `sum = 9; ` `  ``int` `n = ``sizeof``(set)/``sizeof``(set); ` `  ``if` `(isSubsetSum(set, n, sum) == ``true``) ` `     ``printf``(``"Found a subset with given sum"``); ` `  ``else` `     ``printf``(``"No subset with given sum"``); ` `  ``return` `0; ` `} ` `// This code is contributed by Arjun Tyagi. `

## Java

 `// A Dynamic Programming solution for subset ` `// sum problem ` `class` `GFG { ` `     `  `    ``// Returns true if there is a subset of  ` `    ``// set[] with sun equal to given sum ` `    ``static` `boolean` `isSubsetSum(``int` `set[],  ` `                             ``int` `n, ``int` `sum) ` `    ``{ ` `        ``// The value of subset[i][j] will be ` `        ``// true if there is a subset of  ` `        ``// set[0..j-1] with sum equal to i ` `        ``boolean` `subset[][] =  ` `                     ``new` `boolean``[sum+``1``][n+``1``]; ` `     `  `        ``// If sum is 0, then answer is true ` `        ``for` `(``int` `i = ``0``; i <= n; i++) ` `            ``subset[``0``][i] = ``true``; ` `     `  `        ``// If sum is not 0 and set is empty, ` `        ``// then answer is false ` `        ``for` `(``int` `i = ``1``; i <= sum; i++) ` `            ``subset[i][``0``] = ``false``; ` `     `  `        ``// Fill the subset table in botton ` `        ``// up manner ` `        ``for` `(``int` `i = ``1``; i <= sum; i++) ` `        ``{ ` `            ``for` `(``int` `j = ``1``; j <= n; j++) ` `            ``{ ` `                ``subset[i][j] = subset[i][j-``1``]; ` `                ``if` `(i >= set[j-``1``]) ` `                ``subset[i][j] = subset[i][j] ||  ` `                     ``subset[i - set[j-``1``]][j-``1``]; ` `            ``} ` `        ``} ` `     `  `        ``/* // uncomment this code to print table ` `        ``for (int i = 0; i <= sum; i++) ` `        ``{ ` `        ``for (int j = 0; j <= n; j++) ` `            ``System.out.println (subset[i][j]); ` `        ``} */` `     `  `        ``return` `subset[sum][n]; ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main (String args[]) ` `    ``{ ` `        ``int` `set[] = {``3``, ``34``, ``4``, ``12``, ``5``, ``2``}; ` `        ``int` `sum = ``9``; ` `        ``int` `n = set.length; ` `        ``if` `(isSubsetSum(set, n, sum) == ``true``) ` `            ``System.out.println(``"Found a subset"` `                          ``+ ``" with given sum"``); ` `        ``else` `            ``System.out.println(``"No subset with"` `                               ``+ ``" given sum"``); ` `    ``} ` `} ` ` `  `/* This code is contributed by Rajat Mishra */`

## Python3

 `# A Dynamic Programming solution for subset sum problem ` `# Returns true if there is a subset of  ` `# set[] with sun equal to given sum  ` ` `  `# Returns true if there is a subset of set[]  ` `# with sun equal to given sum ` `def` `isSubsetSum(``set``,n,``sum``): ` `     `  `    ``# The value of subset[i][j] will be  ` `    ``# true if there is a ` `    ``# subset of set[0..j-1] with sum equal to i ` `    ``subset``=``([[``False` `for` `i ``in` `range``(``sum``+``1``)]  ` `            ``for` `i ``in` `range``(n``+``1``)]) ` `     `  `    ``# If sum is 0, then answer is true  ` `    ``for` `i ``in` `range``(n``+``1``): ` `        ``subset[i][``0``] ``=` `True` `         `  `        ``# If sum is not 0 and set is empty,  ` `        ``# then answer is false  ` `        ``for` `i ``in` `range``(``1``,``sum``+``1``): ` `            ``subset[``0``][i]``=``False` `             `  `        ``# Fill the subset table in botton up manner ` `        ``for` `i ``in` `range``(``1``,n``+``1``): ` `            ``for` `j ``in` `range``(``1``,``sum``+``1``): ` `                ``if` `j<``set``[i``-``1``]: ` `                    ``subset[i][j] ``=` `subset[i``-``1``][j] ` `                ``if` `j>``=``set``[i``-``1``]: ` `                    ``subset[i][j] ``=` `(subset[i``-``1``][j] ``or`  `                                   ``subset[i ``-` `1``][j``-``set``[i``-``1``]]) ` `     `  `        ``# uncomment this code to print table  ` `        ``# for i in range(n+1): ` `        ``# for j in range(sum+1): ` `        ``#     print (subset[i][j],end=" ") ` `        ``# print() ` `    ``return` `subset[n][``sum``] ` `         `  `# Driver program to test above function ` `if` `__name__``=``=``'__main__'``: ` `    ``set` `=` `[``3``, ``34``, ``4``, ``12``, ``5``, ``2``] ` `    ``sum` `=` `9` `    ``n ``=``len``(``set``) ` `    ``if` `(isSubsetSum(``set``, n, ``sum``) ``=``=` `True``): ` `        ``print``(``"Found a subset with given sum"``) ` `    ``else``: ` `        ``print``(``"No subset with given sum"``) ` `         `  `# This code is contributed by  ` `# sahil shelangia.  `

## C#

 `// A Dynamic Programming solution for subset sum problem ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Returns true if there is a subset  ` `    ``// of set[] with sun equal to given sum ` `    ``static` `bool` `isSubsetSum(``int` `[]``set``, ``int` `n, ``int` `sum) ` `    ``{ ` `        ``// The value of subset[i][j] will be true if there  ` `        ``// is a subset of set[0..j-1] with sum equal to i ` `        ``bool` `[,]subset = ``new` `bool``[sum+1,n+1]; ` `     `  `        ``// If sum is 0, then answer is true ` `        ``for` `(``int` `i = 0; i <= n; i++) ` `        ``subset[0, i] = ``true``; ` `     `  `        ``// If sum is not 0 and set is empty, then answer is false ` `        ``for` `(``int` `i = 1; i <= sum; i++) ` `        ``subset[i, 0] = ``false``; ` `     `  `        ``// Fill the subset table in bottom up manner ` `        ``for` `(``int` `i = 1; i <= sum; i++) ` `        ``{ ` `            ``for` `(``int` `j = 1; j <= n; j++) ` `            ``{ ` `                ``subset[i, j] = subset[i, j - 1]; ` `                ``if` `(i >= ``set``[j - 1]) ` `                ``subset[i, j] = subset[i, j] ||  ` `                               ``subset[i - ``set``[j - 1], j - 1]; ` `                                             `  `            ``} ` `        ``} ` `     `  `        ``return` `subset[sum,n]; ` `    ``} ` `     `  `    ``// Driver program  ` `    ``public` `static` `void` `Main () ` `    ``{ ` `        ``int` `[]``set` `= {3, 34, 4, 12, 5, 2}; ` `        ``int` `sum = 9; ` `        ``int` `n = ``set``.Length; ` `        ``if` `(isSubsetSum(``set``, n, sum) == ``true``) ` `            ``Console.WriteLine(``"Found a subset with given sum"``); ` `        ``else` `            ``Console.WriteLine(``"No subset with given sum"``); ` `    ``} ` `} ` `// This code is contributed by Sam007 `

## PHP

 `= ``\$set``[``\$i``-1]) ` `                ``\$subset``[``\$i``][``\$j``] =  ` `                       ``\$subset``[``\$i``-1][``\$j``] ||  ` `                       ``\$subset``[``\$i` `- 1][``\$j` `-  ` `                               ``\$set``[``\$i``-1]]; ` `        ``} ` `    ``} ` ` `  `    ``/* // uncomment this code to print table ` `    ``for (int i = 0; i <= n; i++) ` `    ``{ ` `    ``for (int j = 0; j <= sum; j++) ` `        ``printf ("%4d", subset[i][j]); ` `    ``printf("n"); ` `    ``}*/` ` `  `    ``return` `\$subset``[``\$n``][``\$sum``]; ` `} ` ` `  `// Driver program to test above function ` `\$set` `= ``array``(3, 34, 4, 12, 5, 2); ` `\$sum` `= 9; ` `\$n` `= ``count``(``\$set``); ` ` `  `if` `(isSubsetSum(``\$set``, ``\$n``, ``\$sum``) == true) ` `    ``echo` `"Found a subset with given sum"``; ` `else` `    ``echo` `"No subset with given sum"``; ` ` `  `// This code is contributed by anuj_67. ` `?> `

Output:

```Found a subset with given sum
```

Time complexity of the above solution is O(sum*n).