# Perfect Sum Problem (Print all subsets with given sum)

Given an array of integers and a sum, the task is to print all subsets of given array with sum equal to given sum.

Examples:

```Input : arr[] = {2, 3, 5, 6, 8, 10}
sum = 10
Output : 5 2 3
2 8
10

Input : arr[] = {1, 2, 3, 4, 5}
sum = 10
Output : 4 3 2 1
5 3 2
5 4 1
```

This problem is mainly an extension of Subset Sum Problem. Here we not only need to find if there is a subset with given sum, but also need to print all subsets with given sum.

Like previous post, we build a 2D array dp[][] such that dp[i][j] stores true if sum j is possible with array elements from 0 to i.
After filling dp[][], we recursively traverse it from dp[n-1][sum]. For cell being traversed, we store path before reaching it and consider two possibilities for the element.
1) Element is included in current path.
2) Element is not included in current path.

Whenever sum becomes 0, we stop the recursive calls and print current path.

Below is implementation of above idea.

## C++

 `// C++ program to count all subsets with ` `// given sum. ` `#include ` `using` `namespace` `std; ` ` `  `// dp[i][j] is going to store true if sum j is ` `// possible with array elements from 0 to i. ` `bool``** dp; ` ` `  `void` `display(``const` `vector<``int``>& v) ` `{ ` `    ``for` `(``int` `i = 0; i < v.size(); ++i) ` `        ``printf``(``"%d "``, v[i]); ` `    ``printf``(````" "````); ` `} ` ` `  `// A recursive function to print all subsets with the ` `// help of dp[][]. Vector p[] stores current subset. ` `void` `printSubsetsRec(``int` `arr[], ``int` `i, ``int` `sum, vector<``int``>& p) ` `{ ` `    ``// If we reached end and sum is non-zero. We print ` `    ``// p[] only if arr is equal to sun OR dp[sum] ` `    ``// is true. ` `    ``if` `(i == 0 && sum != 0 && dp[sum]) ` `    ``{ ` `        ``p.push_back(arr[i]); ` `        ``display(p); ` `        ``return``; ` `    ``} ` ` `  `    ``// If sum becomes 0 ` `    ``if` `(i == 0 && sum == 0) ` `    ``{ ` `        ``display(p); ` `        ``return``; ` `    ``} ` ` `  `    ``// If given sum can be achieved after ignoring ` `    ``// current element. ` `    ``if` `(dp[i-1][sum]) ` `    ``{ ` `        ``// Create a new vector to store path ` `        ``vector<``int``> b = p; ` `        ``printSubsetsRec(arr, i-1, sum, b); ` `    ``} ` ` `  `    ``// If given sum can be achieved after considering ` `    ``// current element. ` `    ``if` `(sum >= arr[i] && dp[i-1][sum-arr[i]]) ` `    ``{ ` `        ``p.push_back(arr[i]); ` `        ``printSubsetsRec(arr, i-1, sum-arr[i], p); ` `    ``} ` `} ` ` `  `// Prints all subsets of arr[0..n-1] with sum 0. ` `void` `printAllSubsets(``int` `arr[], ``int` `n, ``int` `sum) ` `{ ` `    ``if` `(n == 0 || sum < 0) ` `       ``return``; ` ` `  `    ``// Sum 0 can always be achieved with 0 elements ` `    ``dp = ``new` `bool``*[n]; ` `    ``for` `(``int` `i=0; i p; ` `    ``printSubsetsRec(arr, n-1, sum, p); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 2, 3, 4, 5}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``int` `sum = 10; ` `    ``printAllSubsets(arr, n, sum); ` `    ``return` `0; ` `} `

## Java

 `// A Java program to count all subsets with given sum. ` `import` `java.util.ArrayList; ` `public` `class` `SubSet_sum_problem ` `{ ` `    ``// dp[i][j] is going to store true if sum j is ` `    ``// possible with array elements from 0 to i. ` `    ``static` `boolean``[][] dp; ` `      `  `    ``static` `void` `display(ArrayList v) ` `    ``{ ` `       ``System.out.println(v); ` `    ``} ` `      `  `    ``// A recursive function to print all subsets with the ` `    ``// help of dp[][]. Vector p[] stores current subset. ` `    ``static` `void` `printSubsetsRec(``int` `arr[], ``int` `i, ``int` `sum,  ` `                                         ``ArrayList p) ` `    ``{ ` `        ``// If we reached end and sum is non-zero. We print ` `        ``// p[] only if arr is equal to sun OR dp[sum] ` `        ``// is true. ` `        ``if` `(i == ``0` `&& sum != ``0` `&& dp[``0``][sum]) ` `        ``{ ` `            ``p.add(arr[i]); ` `            ``display(p); ` `            ``p.clear(); ` `            ``return``; ` `        ``} ` `      `  `        ``// If sum becomes 0 ` `        ``if` `(i == ``0` `&& sum == ``0``) ` `        ``{ ` `            ``display(p); ` `            ``p.clear(); ` `            ``return``; ` `        ``} ` `      `  `        ``// If given sum can be achieved after ignoring ` `        ``// current element. ` `        ``if` `(dp[i-``1``][sum]) ` `        ``{ ` `            ``// Create a new vector to store path ` `            ``ArrayList b = ``new` `ArrayList<>(); ` `            ``b.addAll(p); ` `            ``printSubsetsRec(arr, i-``1``, sum, b); ` `        ``} ` `      `  `        ``// If given sum can be achieved after considering ` `        ``// current element. ` `        ``if` `(sum >= arr[i] && dp[i-``1``][sum-arr[i]]) ` `        ``{ ` `            ``p.add(arr[i]); ` `            ``printSubsetsRec(arr, i-``1``, sum-arr[i], p); ` `        ``} ` `    ``} ` `      `  `    ``// Prints all subsets of arr[0..n-1] with sum 0. ` `    ``static` `void` `printAllSubsets(``int` `arr[], ``int` `n, ``int` `sum) ` `    ``{ ` `        ``if` `(n == ``0` `|| sum < ``0``) ` `           ``return``; ` `      `  `        ``// Sum 0 can always be achieved with 0 elements ` `        ``dp = ``new` `boolean``[n][sum + ``1``]; ` `        ``for` `(``int` `i=``0``; i p = ``new` `ArrayList<>(); ` `        ``printSubsetsRec(arr, n-``1``, sum, p); ` `    ``} ` `     `  `    ``//Driver Program to test above functions ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `arr[] = {``1``, ``2``, ``3``, ``4``, ``5``}; ` `        ``int` `n = arr.length; ` `        ``int` `sum = ``10``; ` `        ``printAllSubsets(arr, n, sum); ` `    ``} ` `} ` `//This code is contributed by Sumit Ghosh `

Output :

```4 3 2 1
5 3 2
5 4 1
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.