# Find all distinct subset (or subsequence) sums of an array

Given a set of integers, find distinct sum that can be generated from the subsets of the given sets and print them in an increasing order. It is given that sum of array elements is small.

Examples:

```Input  : arr[] = {1, 2, 3}
Output : 0 1 2 3 4 5 6
Distinct subsets of given set are
{}, {1}, {2}, {3}, {1,2}, {2,3},
{1,3} and {1,2,3}.  Sums of these
subsets are 0, 1, 2, 3, 3, 5, 4, 6
After removing duplicates, we get
0, 1, 2, 3, 4, 5, 6

Input : arr[] = {2, 3, 4, 5, 6}
Output : 0 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 20

Input : arr[] = {20, 30, 50}
Output : 0 20 30 50 70 80 100
```

The naive solution for this problem is to generate all the subsets, store their sums in a hash set and finally print all keys from hash set.

## C++

 `// C++ program to print distinct subset sums of ` `// a given array. ` `#include ` `using` `namespace` `std; ` ` `  `// sum denotes the current sum of the subset ` `// currindex denotes the index we have reached in ` `// the given array ` `void` `distSumRec(``int` `arr[], ``int` `n, ``int` `sum, ` `                ``int` `currindex, unordered_set<``int``> &s) ` `{ ` `    ``if` `(currindex > n) ` `        ``return``; ` ` `  `    ``if` `(currindex == n) ` `    ``{ ` `        ``s.insert(sum); ` `        ``return``; ` `    ``} ` ` `  `    ``distSumRec(arr, n, sum + arr[currindex], ` `                            ``currindex+1, s); ` `    ``distSumRec(arr, n, sum, currindex+1, s); ` `} ` ` `  `// This function mainly calls recursive function ` `// distSumRec() to generate distinct sum subsets. ` `// And finally prints the generated subsets. ` `void` `printDistSum(``int` `arr[], ``int` `n) ` `{ ` `    ``unordered_set<``int``> s; ` `    ``distSumRec(arr, n, 0, 0, s); ` ` `  `    ``// Print the result ` `    ``for` `(``auto` `i=s.begin(); i!=s.end(); i++) ` `        ``cout << *i << ``" "``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {2, 3, 4, 5, 6}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``printDistSum(arr, n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to print distinct ` `// subset sums of a given array. ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` `    ``// sum denotes the current sum  ` `    ``// of the subset currindex denotes  ` `    ``// the index we have reached in ` `    ``// the given array ` `    ``static` `void` `distSumRec(``int` `arr[], ``int` `n, ``int` `sum, ` `                          ``int` `currindex, HashSet s) ` `    ``{ ` `        ``if` `(currindex > n) ` `            ``return``; ` ` `  `        ``if` `(currindex == n) { ` `            ``s.add(sum); ` `            ``return``; ` `        ``} ` ` `  `        ``distSumRec(arr, n, sum + arr[currindex], ` `                    ``currindex + ``1``, s); ` `        ``distSumRec(arr, n, sum, currindex + ``1``, s); ` `    ``} ` ` `  `    ``// This function mainly calls  ` `    ``// recursive function distSumRec()  ` `    ``// to generate distinct sum subsets. ` `    ``// And finally prints the generated subsets. ` `    ``static` `void` `printDistSum(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``HashSet s = ``new` `HashSet<>(); ` `        ``distSumRec(arr, n, ``0``, ``0``, s); ` ` `  `        ``// Print the result ` `        ``for` `(``int` `i : s) ` `            ``System.out.print(i + ``" "``); ` `    ``} ` `     `  `    ``//Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``2``, ``3``, ``4``, ``5``, ``6` `}; ` `        ``int` `n = arr.length; ` `        ``printDistSum(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed by Gitanjali. `

## Python3

 `# Python 3 program to print distinct subset sums of ` `# a given array. ` ` `  `# sum denotes the current sum of the subset ` `# currindex denotes the index we have reached in ` `# the given array ` `def` `distSumRec(arr, n, ``sum``, currindex, s): ` `    ``if` `(currindex > n): ` `        ``return` ` `  `    ``if` `(currindex ``=``=` `n): ` `        ``s.add(``sum``) ` `        ``return` ` `  `    ``distSumRec(arr, n, ``sum` `+` `arr[currindex], currindex``+``1``, s) ` `    ``distSumRec(arr, n, ``sum``, currindex``+``1``, s) ` ` `  `# This function mainly calls recursive function ` `# distSumRec() to generate distinct sum subsets. ` `# And finally prints the generated subsets. ` `def` `printDistSum(arr,n): ` `    ``s ``=` `set``() ` `    ``distSumRec(arr, n, ``0``, ``0``, s) ` ` `  `    ``# Print the result ` `    ``for` `i ``in` `s: ` `        ``print``(i,end ``=` `" "``) ` ` `  `# Driver code ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``arr ``=` `[``2``, ``3``, ``4``, ``5``, ``6``] ` `    ``n ``=` `len``(arr) ` `    ``printDistSum(arr, n) ` ` `  `# This code is contributed by ` `# Surendra_Gangwar `

## C#

 `// C# program to print distinct ` `// subset sums of a given array. ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG  ` `{ ` `    ``// sum denotes the current sum  ` `    ``// of the subset currindex denotes  ` `    ``// the index we have reached in ` `    ``// the given array ` `    ``static` `void` `distSumRec(``int` `[]arr, ``int` `n, ``int` `sum, ` `                        ``int` `currindex, HashSet<``int``> s) ` `    ``{ ` `        ``if` `(currindex > n) ` `            ``return``; ` ` `  `        ``if` `(currindex == n)  ` `        ``{ ` `            ``s.Add(sum); ` `            ``return``; ` `        ``} ` ` `  `        ``distSumRec(arr, n, sum + arr[currindex], ` `                    ``currindex + 1, s); ` `        ``distSumRec(arr, n, sum, currindex + 1, s); ` `    ``} ` ` `  `    ``// This function mainly calls  ` `    ``// recursive function distSumRec()  ` `    ``// to generate distinct sum subsets. ` `    ``// And finally prints the generated subsets. ` `    ``static` `void` `printDistSum(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``HashSet<``int``> s = ``new` `HashSet<``int``>(); ` `        ``distSumRec(arr, n, 0, 0, s); ` ` `  `        ``// Print the result ` `        ``foreach` `(``int` `i ``in` `s) ` `            ``Console.Write(i + ``" "``); ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = { 2, 3, 4, 5, 6 }; ` `        ``int` `n = arr.Length; ` `        ``printDistSum(arr, n); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

Output:

```0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20
```

Time complexity of the above naive recursive approach is O(2n).

Time complexity of the above problem can be improved using Dynamic Programming, especially when sum of given elements is small. We can make a dp table with rows containing the size of the array and size of the column will be sum of all the elements in the array.

## C++

 `// C++ program to print distinct subset sums of ` `// a given array. ` `#include ` `using` `namespace` `std; ` ` `  `// Uses Dynamic Programming to find distinct ` `// subset sums ` `void` `printDistSum(``int` `arr[], ``int` `n) ` `{ ` `    ``int` `sum = 0; ` `    ``for` `(``int` `i=0; i

## Java

 `// Java program to print distinct ` `// subset sums of a given array. ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// Uses Dynamic Programming to ` `    ``// find distinct subset sums ` `    ``static` `void` `printDistSum(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``int` `sum = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``sum += arr[i]; ` ` `  `        ``// dp[i][j] would be true if arr[0..i-1]  ` `        ``// has a subset with sum equal to j. ` `        ``boolean``[][] dp = ``new` `boolean``[n + ``1``][sum + ``1``]; ` ` `  `        ``// There is always a subset with 0 sum ` `        ``for` `(``int` `i = ``0``; i <= n; i++) ` `            ``dp[i][``0``] = ``true``; ` ` `  `        ``// Fill dp[][] in bottom up manner ` `        ``for` `(``int` `i = ``1``; i <= n; i++)  ` `        ``{ ` `            ``dp[i][arr[i - ``1``]] = ``true``; ` `            ``for` `(``int` `j = ``1``; j <= sum; j++)  ` `            ``{ ` `                ``// Sums that were achievable ` `                ``// without current array element ` `                ``if` `(dp[i - ``1``][j] == ``true``)  ` `                ``{ ` `                    ``dp[i][j] = ``true``; ` `                    ``dp[i][j + arr[i - ``1``]] = ``true``; ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// Print last row elements ` `        ``for` `(``int` `j = ``0``; j <= sum; j++) ` `            ``if` `(dp[n][j] == ``true``) ` `                ``System.out.print(j + ``" "``); ` `    ``} ` ` `  `        ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``2``, ``3``, ``4``, ``5``, ``6` `}; ` `        ``int` `n = arr.length; ` `        ``printDistSum(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed by Gitanjali. `

## Python3

 `# Python3 program to prdistinct subset  ` `# Sums of a given array.  ` ` `  `# Uses Dynamic Programming to find  ` `# distinct subset Sums  ` `def` `printDistSum(arr, n): ` ` `  `    ``Sum` `=` `sum``(arr) ` `     `  `    ``# dp[i][j] would be true if arr[0..i-1]  ` `    ``# has a subset with Sum equal to j.  ` `    ``dp ``=` `[[``False` `for` `i ``in` `range``(``Sum` `+` `1``)]  ` `                 ``for` `i ``in` `range``(n ``+` `1``)] ` `                  `  `    ``# There is always a subset with 0 Sum  ` `    ``for` `i ``in` `range``(n ``+` `1``):  ` `        ``dp[i][``0``] ``=` `True` ` `  `    ``# Fill dp[][] in bottom up manner  ` `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` ` `  `        ``dp[i][arr[i ``-` `1``]] ``=` `True` ` `  `        ``for` `j ``in` `range``(``1``, ``Sum` `+` `1``): ` `             `  `            ``# Sums that were achievable  ` `            ``# without current array element  ` `            ``if` `(dp[i ``-` `1``][j] ``=``=` `True``): ` `                ``dp[i][j] ``=` `True` `                ``dp[i][j ``+` `arr[i ``-` `1``]] ``=` `True` `             `  `    ``# Print last row elements  ` `    ``for` `j ``in` `range``(``Sum` `+` `1``):  ` `        ``if` `(dp[n][j] ``=``=` `True``): ` `            ``print``(j, end ``=` `" "``) ` ` `  `# Driver code  ` `arr ``=` `[``2``, ``3``, ``4``, ``5``, ``6``]  ` `n ``=` `len``(arr) ` `printDistSum(arr, n)  ` ` `  `# This code is contributed  ` `# by mohit kumar `

## C#

 `// C# program to print distinct ` `// subset sums of a given array. ` `using` `System; ` `  `  `class` `GFG { ` `  `  `    ``// Uses Dynamic Programming to ` `    ``// find distinct subset sums ` `    ``static` `void` `printDistSum(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``int` `sum = 0; ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``sum += arr[i]; ` `  `  `        ``// dp[i][j] would be true if arr[0..i-1]  ` `        ``// has a subset with sum equal to j. ` `        ``bool` `[,]dp = ``new` `bool``[n + 1,sum + 1]; ` `  `  `        ``// There is always a subset with 0 sum ` `        ``for` `(``int` `i = 0; i <= n; i++) ` `            ``dp[i,0] = ``true``; ` `  `  `        ``// Fill dp[][] in bottom up manner ` `        ``for` `(``int` `i = 1; i <= n; i++)  ` `        ``{ ` `            ``dp[i,arr[i - 1]] = ``true``; ` `            ``for` `(``int` `j = 1; j <= sum; j++)  ` `            ``{ ` `                ``// Sums that were achievable ` `                ``// without current array element ` `                ``if` `(dp[i - 1,j] == ``true``)  ` `                ``{ ` `                    ``dp[i,j] = ``true``; ` `                    ``dp[i,j + arr[i - 1]] = ``true``; ` `                ``} ` `            ``} ` `        ``} ` `  `  `        ``// Print last row elements ` `        ``for` `(``int` `j = 0; j <= sum; j++) ` `            ``if` `(dp[n,j] == ``true``) ` `                ``Console.Write(j + ``" "``); ` `    ``} ` `  `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = { 2, 3, 4, 5, 6 }; ` `        ``int` `n = arr.Length; ` `        ``printDistSum(arr, n); ` `    ``} ` `} ` `  `  `// This code is contributed by nitin mittal. `

Output:

```0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20
```

Time complexity of the above approach is O(n*sum) where n is the size of the array and sum is the sum of all the integers in the array.