# Maximum size subset with given sum

This is an extended version of subset sum problem. Here we need to find size of maximum size subset whose sum is equal to given sum.

Examples:

```Input : set[] = {2, 3, 5, 7, 10, 15},
sum  = 10
Output : 3
The largest sized subset with sum 10
is {2, 3, 5}

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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

This is the further enhancement to subset sum problem which not only tells whether the subset is possible but also the maximal subset using DP.

To solve the subset sum problem, use the same DP approach as given in subset sum problem. To further count the maximal subset, we use another DP array (called as ‘count array’) where count[i][j] is maximal of

• count[i][j-1]. Here current element is not considered.
• count[i- X][j-1] + 1. Here X is value of the current element selected for subset.

## C++

 `// A Dynamic Programming solution for subset  ` `// sum problem+ maximal subset value. ` `#include ` `using` `namespace` `std; ` ` `  `    ``// Returns size of maximum sized subset  ` `    ``// if there is a subset of set[] with sun  ` `    ``// equal to given sum. It returns -1 if there  ` `    ``// is no subset with given sum.  ` `    ``int` `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[sum + 1][n + 1];  ` `        ``int` `count[sum + 1][n + 1];  ` ` `  `        ``// If sum is 0, then answer is true  ` `        ``for` `(``int` `i = 0; i <= n; i++)  ` `        ``{  ` `            ``subset[i] = ``true``;  ` `            ``count[i] = 0;  ` `        ``}  ` `     `  `        ``// If sum is not 0 and set is empty,  ` `        ``// then answer is false  ` `        ``for` `(``int` `i = 1; i <= sum; i++)  ` `        ``{  ` `            ``subset[i] = ``false``;  ` `            ``count[i] = -1;  ` `        ``}  ` ` `  `        ``// 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];  ` `                ``count[i][j] = count[i][j - 1];  ` `                ``if` `(i >= set[j - 1])  ` `                ``{  ` `                    ``subset[i][j] = subset[i][j] ||  ` `                                ``subset[i - set[j - 1]][j - 1];  ` ` `  `                    ``if` `(subset[i][j])  ` `                        ``count[i][j] = max(count[i][j - 1],  ` `                                    ``count[i - set[j - 1]][j - 1] + 1);  ` `                ``}  ` `            ``}  ` `        ``}  ` ` `  `        ``return` `count[sum][n];  ` `    ``}  ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `set[] = { 2, 3, 5, 10 };  ` `    ``int` `sum = 20;  ` `    ``int` `n = 4;  ` `    ``cout<< isSubsetSum(set, n, sum);  ` `} ` ` `  `// This code is contributed by DrRoot_ `

## Java

 `// A Dynamic Programming solution for subset  ` `// sum problem+ maximal subset value. ` `class` `sumofSub { ` ` `  `    ``// Returns size of maximum sized subset if there ` `    ``// is a subset of set[] with sun equal to given sum. ` `    ``// It returns -1 if there is no subset with given sum. ` `    ``static` `int` `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``]; ` `        ``int` `count[][] = ``new` `int``[sum + ``1``][n + ``1``]; ` ` `  `        ``// If sum is 0, then answer is true ` `        ``for` `(``int` `i = ``0``; i <= n; i++) { ` `            ``subset[``0``][i] = ``true``; ` `            ``count[``0``][i] = ``0``; ` `        ``} ` ` `  `        ``// If sum is not 0 and set is empty, ` `        ``// then answer is false ` `        ``for` `(``int` `i = ``1``; i <= sum; i++) { ` `            ``subset[i][``0``] = ``false``; ` `            ``count[i][``0``] = -``1``; ` `        ``} ` ` `  `        ``// 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``]; ` `                ``count[i][j] = count[i][j - ``1``]; ` `                ``if` `(i >= set[j - ``1``]) { ` `                    ``subset[i][j] = subset[i][j] ||  ` `                       ``subset[i - set[j - ``1``]][j - ``1``]; ` ` `  `                    ``if` `(subset[i][j]) ` `                        ``count[i][j] = Math.max(count[i][j - ``1``], ` `                             ``count[i - set[j - ``1``]][j - ``1``] + ``1``); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``return` `count[sum][n]; ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `set[] = { ``2``, ``3``, ``5``, ``10` `}; ` `        ``int` `sum = ``20``; ` `        ``int` `n = set.length; ` `        ``System.out.println(isSubsetSum(set, n, sum)); ` `    ``} ` `} `

## C#

 `// A Dynamic Programming solution for subset ` `// sum problem+ maximal subset value. ` `using` `System; ` ` `  `class` `sumofSub { ` ` `  `    ``// Returns size of maximum sized subset  ` `    ``// if there is a subset of set[] with sun  ` `    ``// equal to given sum. It returns -1 if there ` `    ``// is no subset with given sum. ` `    ``static` `int` `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]; ` `        ``int``[, ] count = ``new` `int``[sum + 1, n + 1]; ` ` `  `        ``// If sum is 0, then answer is true ` `        ``for` `(``int` `i = 0; i <= n; i++) { ` `            ``subset[0, i] = ``true``; ` `            ``count[0, i] = 0; ` `        ``} ` ` `  `        ``// If sum is not 0 and set is empty, ` `        ``// then answer is false ` `        ``for` `(``int` `i = 1; i <= sum; i++) { ` `            ``subset[i, 0] = ``false``; ` `            ``count[i, 0] = -1; ` `        ``} ` ` `  `        ``// 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]; ` `                ``count[i, j] = count[i, j - 1]; ` `                ``if` `(i >= ``set``[j - 1]) { ` `                    ``subset[i, j] = subset[i, j] ||  ` `                                   ``subset[i - ``set``[j - 1], j - 1]; ` ` `  `                    ``if` `(subset[i, j]) ` `                        ``count[i, j] = Math.Max(count[i, j - 1], ` `                                      ``count[i - ``set``[j - 1], j - 1] + 1); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``return` `count[sum, n]; ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] ``set` `= { 2, 3, 5, 10 }; ` `        ``int` `sum = 20; ` `        ``int` `n = ``set``.Length; ` `        ``Console.WriteLine(isSubsetSum(``set``, n, sum)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

Output:

```4
```

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