# 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 
```

```java
// Array contains non-negative integers
public class solution {
    public static void printer(int[] arr, boolean[][] dp, ArrayList<Integer> temp, int n, int sum) {
        if (n == 0) {
            if (sum == 0)
                System.out.println(temp);
            return;
        } else if (sum == 0) {
            System.out.println(temp);
            return;
        }

        if (dp[n - 1][sum])
            printer(arr, dp, temp, n - 1, sum);
        if (sum - arr[n - 1] >= 0 && dp[n - 1][sum - arr[n - 1]]) {
            temp.add(0, arr[n - 1]);
            printer(arr, dp, temp, n - 1, sum - arr[n - 1]);
            temp.remove(0);
        }
    }

    public static void printSumToK(int[] arr, int n, int sum) {
        boolean dp[][] = new boolean[n + 1][sum + 1];
        // Base case -> if sum=0 then ans=True
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= sum; k++) {
                if (arr[i - 1] <= k)
                    dp[i][k] = (dp[i - 1][k] || dp[i - 1][k - arr[i - 1]]);
                else
                    dp[i][k] = dp[i - 1][k];
            }
        }
        if (dp[n][sum]) {
            printer(arr, dp, new ArrayList<Integer>(), n, sum);
        }
    }
}
```
