# Partition problem | DP-18

Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

Examples:

```arr[] = {1, 5, 11, 5}
Output: true
The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}
Output: false
The array cannot be partitioned into equal sum sets.
```

## We strongly recommend that you click here and practice it, before moving on to the solution.

Following are the two main steps to solve this problem:
1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

Recursive Solution
Following is the recursive property of the second step mentioned above.

```Let isSubsetSum(arr, n, sum/2) be the function that returns true if
there is a subset of arr[0..n-1] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems
a) isSubsetSum() without considering last element
(reducing n to n-1)
b) isSubsetSum considering the last element
(reducing sum/2 by arr[n-1] and n to n-1)
If any of the above the above subproblems return true, then return true.
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
isSubsetSum (arr, n-1, sum/2 - arr[n-1])
```

## C++

 `// A recursive C++ program for partition problem  ` `#include ` `using` `namespace` `std; ` ` `  `// A utility function that returns true if there is  ` `// a subset of arr[] with sun equal to given sum  ` `bool` `isSubsetSum (``int` `arr[], ``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` `(arr[n-1] > sum)  ` `       ``return` `isSubsetSum (arr, 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 (arr, n-1, sum) ||  ` `        ``isSubsetSum (arr, n-1, sum-arr[n-1]);  ` `}  ` ` `  `// Returns true if arr[] can be partitioned in two  ` `// subsets of equal sum, otherwise false  ` `bool` `findPartiion (``int` `arr[], ``int` `n)  ` `{  ` `    ``// Calculate sum of the elements in array  ` `    ``int` `sum = 0;  ` `    ``for` `(``int` `i = 0; i < n; i++)  ` `    ``sum += arr[i];  ` ` `  `    ``// If sum is odd, there cannot be two subsets  ` `    ``// with equal sum  ` `    ``if` `(sum%2 != 0)  ` `    ``return` `false``;  ` ` `  `    ``// Find if there is subset with sum equal to  ` `    ``// half of total sum  ` `    ``return` `isSubsetSum (arr, n, sum/2);  ` `}  ` ` `  `// Driver program to test above function  ` `int` `main()  ` `{  ` `    ``int` `arr[] = {3, 1, 5, 9, 12};  ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);  ` `    ``if` `(findPartiion(arr, n) == ``true``)  ` `        ``cout << ``"Can be divided into two subsets "` `                ``"of equal sum"``;  ` `    ``else` `        ``cout << ``"Can not be divided into two subsets"` `                ``" of equal sum"``;  ` `    ``return` `0;  ` `}  ` ` `  `// This code is contributed by rathbhupendra `

## C

 `// A  recursive C program for partition problem ` `#include ` `#include ` ` `  `// A utility function that returns true if there is  ` `// a subset of arr[] with sun equal to given sum ` `bool` `isSubsetSum (``int` `arr[], ``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` `(arr[n-1] > sum) ` `     ``return` `isSubsetSum (arr, 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 (arr, n-1, sum) ||  ` `          ``isSubsetSum (arr, n-1, sum-arr[n-1]); ` `} ` ` `  `// Returns true if arr[] can be partitioned in two ` `//  subsets of equal sum, otherwise false ` `bool` `findPartiion (``int` `arr[], ``int` `n) ` `{ ` `    ``// Calculate sum of the elements in array ` `    ``int` `sum = 0; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `       ``sum += arr[i]; ` ` `  `    ``// If sum is odd, there cannot be two subsets  ` `    ``// with equal sum ` `    ``if` `(sum%2 != 0) ` `       ``return` `false``; ` ` `  `    ``// Find if there is subset with sum equal to ` `    ``// half of total sum ` `    ``return` `isSubsetSum (arr, n, sum/2); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `  ``int` `arr[] = {3, 1, 5, 9, 12}; ` `  ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `  ``if` `(findPartiion(arr, n) == ``true``) ` `     ``printf``(``"Can be divided into two subsets "` `            ``"of equal sum"``); ` `  ``else` `     ``printf``(``"Can not be divided into two subsets"` `            ``" of equal sum"``); ` `  ``return` `0; ` `} `

## Java

 `// A recursive Java solution for partition problem ` `import` `java.io.*; ` ` `  `class` `Partition ` `{ ` `    ``// A utility function that returns true if there is a ` `    ``// subset of arr[] with sun equal to given sum ` `    ``static` `boolean` `isSubsetSum (``int` `arr[], ``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` `(arr[n-``1``] > sum) ` `            ``return` `isSubsetSum (arr, 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 (arr, n-``1``, sum) || ` `               ``isSubsetSum (arr, n-``1``, sum-arr[n-``1``]); ` `    ``} ` ` `  `    ``// Returns true if arr[] can be partitioned in two ` `    ``// subsets of equal sum, otherwise false ` `    ``static` `boolean` `findPartition (``int` `arr[], ``int` `n) ` `    ``{ ` `        ``// Calculate sum of the elements in array ` `        ``int` `sum = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``sum += arr[i]; ` ` `  `        ``// If sum is odd, there cannot be two subsets ` `        ``// with equal sum ` `        ``if` `(sum%``2` `!= ``0``) ` `            ``return` `false``; ` ` `  `        ``// Find if there is subset with sum equal to half ` `        ``// of total sum ` `        ``return` `isSubsetSum (arr, n, sum/``2``); ` `    ``} ` ` `  `    ``/*Driver function to check for above function*/` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` ` `  `        ``int` `arr[] = {``3``, ``1``, ``5``, ``9``, ``12``}; ` `        ``int` `n = arr.length; ` `        ``if` `(findPartition(arr, n) == ``true``) ` `            ``System.out.println(``"Can be divided into two "``+ ` `                                ``"subsets of equal sum"``); ` `        ``else` `            ``System.out.println(``"Can not be divided into "` `+ ` `                                ``"two subsets of equal sum"``); ` `    ``} ` `} ` `/* This code is contributed by Devesh Agrawal */`

## Python3

 `# A recursive Python3 program for  ` `# partition problem ` ` `  `# A utility function that returns  ` `# true if there is a subset of ` `# arr[] with sun equal to given sum ` `def` `isSubsetSum (arr, 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` `arr[n``-``1``] > ``sum``: ` `        ``return` `isSubsetSum (arr, 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 (arr, n``-``1``, ``sum``) ``or` `isSubsetSum (arr, n``-``1``, ``sum``-``arr[n``-``1``]) ` ` `  `# Returns true if arr[] can be partitioned in two ` `# subsets of equal sum, otherwise false ` `def` `findPartion (arr, n): ` `    ``# Calculate sum of the elements in array ` `    ``sum` `=` `0` `    ``for` `i ``in` `range``(``0``, n): ` `        ``sum` `+``=` `arr[i] ` `    ``# If sum is odd, there cannot be two subsets  ` `    ``# with equal sum ` `    ``if` `sum` `%` `2` `!``=` `0``: ` `        ``return` `false ` ` `  `    ``# Find if there is subset with sum equal to ` `    ``# half of total sum ` `    ``return` `isSubsetSum (arr, n, ``sum` `/``/` `2``) ` ` `  `# Driver program to test above function ` `arr ``=` `[``3``, ``1``, ``5``, ``9``, ``12``] ` `n ``=` `len``(arr) ` `if` `findPartion(arr, n) ``=``=` `True``: ` `    ``print` `(``"Can be divided into two subsets of equal sum"``) ` `else``: ` `    ``print` `(``"Can not be divided into two subsets of equal sum"``) ` `     `  `# This code is contributed by shreyanshi_arun.      `

## C#

 `// A recursive C# solution for partition problem ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// A utility function that returns true if there is a ` `    ``// subset of arr[] with sun equal to given sum ` `    ``static` `bool` `isSubsetSum (``int` `[]arr, ``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` `(arr[n-1] > sum) ` `            ``return` `isSubsetSum (arr, 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 (arr, n-1, sum) || ` `               ``isSubsetSum (arr, n-1, sum-arr[n-1]); ` `    ``} ` ` `  `    ``// Returns true if arr[] can be partitioned in two ` `    ``// subsets of equal sum, otherwise false ` `    ``static` `bool` `findPartition (``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``// Calculate sum of the elements in array ` `        ``int` `sum = 0; ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``sum += arr[i]; ` ` `  `        ``// If sum is odd, there cannot be two subsets ` `        ``// with equal sum ` `        ``if` `(sum%2 != 0) ` `            ``return` `false``; ` ` `  `        ``// Find if there is subset with sum equal to half ` `        ``// of total sum ` `        ``return` `isSubsetSum (arr, n, sum/2); ` `    ``} ` ` `  `    ``// Driver function  ` `    ``public` `static` `void` `Main () ` `    ``{ ` ` `  `        ``int` `[]arr = {3, 1, 5, 9, 12}; ` `        ``int` `n = arr.Length; ` `        ``if` `(findPartition(arr, n) == ``true``) ` `            ``Console.Write(``"Can be divided into two "``+ ` `                          ``"subsets of equal sum"``); ` `        ``else` `            ``Console.Write(``"Can not be divided into "` `+ ` `                          ``"two subsets of equal sum"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` ``\$sum``)  ` `        ``return` `isSubsetSum (``\$arr``, ``\$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 (``\$arr``, ``\$n` `- 1, ``\$sum``) ||  ` `           ``isSubsetSum (``\$arr``, ``\$n` `- 1,  ` `                        ``\$sum` `- ``\$arr``[``\$n` `- 1]);  ` `}   ` ` `  `// Returns true if arr[] can be partitioned  ` `// in two subsets of equal sum, otherwise false  ` `function` `findPartiion (``\$arr``, ``\$n``)  ` `{  ` `    ``// Calculate sum of the elements ` `    ``// in array  ` `    ``\$sum` `= 0;  ` `    ``for` `(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++)  ` `    ``\$sum` `+= ``\$arr``[``\$i``];  ` ` `  `    ``// If sum is odd, there cannot be  ` `    ``// two subsets with equal sum  ` `    ``if` `(``\$sum` `% 2 != 0)  ` `    ``return` `false;  ` ` `  `    ``// Find if there is subset with sum ` `    ``// equal to half of total sum  ` `    ``return` `isSubsetSum (``\$arr``, ``\$n``, ``\$sum` `/ 2);  ` `}  ` ` `  `// Driver Code ` `\$arr` `= ``array``(3, 1, 5, 9, 12);  ` `\$n` `= ``count``(``\$arr``);  ` `if` `(findPartiion(``\$arr``, ``\$n``) == true)  ` `    ``echo` `"Can be divided into two subsets of equal sum"``;  ` `else` `    ``echo` `"Can not be divided into two subsets of equal sum"``;  ` ` `  `// This code is contributed by rathbhupendra ` `?> `

Output:

`Can be divided into two subsets of equal sum`

Time Complexity: O(2^n) In worst case, this solution tries two possibilities (whether to include or exclude) for every element.

Dynamic Programming Solution
The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array part[][] of size (sum/2)*(n+1). And we can construct the solution in bottom up manner such that every filled entry has following property

```part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum
equal to i, otherwise false
```

## C/C++

 `// A Dynamic Programming based C program to partition problem ` `#include ` ` `  `// Returns true if arr[] can be partitioned in two subsets of ` `// equal sum, otherwise false ` `bool` `findPartiion (``int` `arr[], ``int` `n) ` `{ ` `    ``int` `sum = 0; ` `    ``int` `i, j; ` `   `  `    ``// Caculcate sun of all elements ` `    ``for` `(i = 0; i < n; i++) ` `      ``sum += arr[i]; ` `     `  `    ``if` `(sum%2 != 0)   ` `       ``return` `false``; ` `   `  `    ``bool` `part[sum/2+1][n+1]; ` `     `  `    ``// initialize top row as true ` `    ``for` `(i = 0; i <= n; i++) ` `      ``part[0][i] = ``true``; ` `       `  `    ``// initialize leftmost column, except part[0][0], as 0 ` `    ``for` `(i = 1; i <= sum/2; i++) ` `      ``part[i][0] = ``false``;      ` `      `  `     ``// Fill the partition table in botton up manner  ` `     ``for` `(i = 1; i <= sum/2; i++)   ` `     ``{ ` `       ``for` `(j = 1; j <= n; j++)   ` `       ``{ ` `         ``part[i][j] = part[i][j-1]; ` `         ``if` `(i >= arr[j-1]) ` `           ``part[i][j] = part[i][j] || part[i - arr[j-1]][j-1]; ` `       ``}         ` `     ``}     ` `      `  `    ``/* // uncomment this part to print table  ` `     ``for (i = 0; i <= sum/2; i++)   ` `     ``{ ` `       ``for (j = 0; j <= n; j++)   ` `          ``printf ("%4d", part[i][j]); ` `       ````printf(" "); ``` `     ``} */`  `      `  `     ``return` `part[sum/2][n]; ` `}      ` ` `  `// Driver program to test above funtion ` `int` `main() ` `{ ` `  ``int` `arr[] = {3, 1, 1, 2, 2, 1}; ` `  ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `  ``if` `(findPartiion(arr, n) == ``true``) ` `     ``printf``(``"Can be divided into two subsets of equal sum"``); ` `  ``else` `     ``printf``(``"Can not be divided into two subsets of equal sum"``); ` `  ``getchar``(); ` `  ``return` `0; ` `} `

## Java

 `// A dynamic programming based Java program for partition problem ` `import` `java.io.*; ` ` `  `class` `Partition { ` ` `  `    ``// Returns true if arr[] can be partitioned in two subsets of ` `    ``// equal sum, otherwise false ` `    ``static` `boolean` `findPartition (``int` `arr[], ``int` `n) ` `    ``{ ` `        ``int` `sum = ``0``; ` `        ``int` `i, j; ` ` `  `        ``// Caculcate sun of all elements ` `        ``for` `(i = ``0``; i < n; i++) ` `            ``sum += arr[i]; ` ` `  `        ``if` `(sum%``2` `!= ``0``) ` `            ``return` `false``; ` ` `  `        ``boolean` `part[][]=``new` `boolean``[sum/``2``+``1``][n+``1``]; ` ` `  `        ``// initialize top row as true ` `        ``for` `(i = ``0``; i <= n; i++) ` `            ``part[``0``][i] = ``true``; ` ` `  `        ``// initialize leftmost column, except part[0][0], as 0 ` `        ``for` `(i = ``1``; i <= sum/``2``; i++) ` `            ``part[i][``0``] = ``false``; ` ` `  `        ``// Fill the partition table in botton up manner ` `        ``for` `(i = ``1``; i <= sum/``2``; i++) ` `        ``{ ` `            ``for` `(j = ``1``; j <= n; j++) ` `            ``{ ` `                ``part[i][j] = part[i][j-``1``]; ` `                ``if` `(i >= arr[j-``1``]) ` `                    ``part[i][j] = part[i][j] || ` `                                 ``part[i - arr[j-``1``]][j-``1``]; ` `            ``} ` `        ``} ` ` `  `        ``/* // uncomment this part to print table ` `        ``for (i = 0; i <= sum/2; i++) ` `        ``{ ` `            ``for (j = 0; j <= n; j++) ` `                ``printf ("%4d", part[i][j]); ` `            ````printf(" "); ``` `        ``} */` ` `  `        ``return` `part[sum/``2``][n]; ` `    ``} ` ` `  `    ``/*Driver function to check for above function*/` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``int` `arr[] = {``3``, ``1``, ``1``, ``2``, ``2``,``1``}; ` `        ``int` `n = arr.length; ` `        ``if` `(findPartition(arr, n) == ``true``) ` `            ``System.out.println(``"Can be divided into two "` `                               ``"subsets of equal sum"``); ` `        ``else` `            ``System.out.println(``"Can not be divided into"` `                            ``" two subsets of equal sum"``); ` ` `  `    ``} ` `} ` `/* This code is contributed by Devesh Agrawal */`

## Python3

 `# Dynamic Programming based python  ` `# program to partition problem ` ` `  `# Returns true if arr[] can be  ` `# partitioned in two subsets of  ` `# equal sum, otherwise false ` `def` `findPartition(arr, n): ` `    ``sum` `=` `0` `    ``i, j ``=` `0``, ``0` `     `  `    ``# calculate sum of all elements ` `    ``for` `i ``in` `range``(n): ` `        ``sum` `+``=` `arr[i] ` `     `  `    ``if` `sum` `%` `2` `!``=` `0``: ` `        ``return` `false ` `     `  `    ``part ``=` `[[ ``True` `for` `i ``in` `range``(n ``+` `1``)]  ` `                   ``for` `j ``in` `range``(``sum` `/``/` `2` `+` `1``)] ` `     `  `    ``# initialize top row as true ` `    ``for` `i ``in` `range``(``0``, n ``+` `1``): ` `        ``part[``0``][i] ``=` `True` `         `  `    ``# intialize leftmost column,  ` `    ``# except part[0][0], as 0 ` `    ``for` `i ``in` `range``(``1``, ``sum` `/``/` `2` `+` `1``): ` `        ``part[i][``0``] ``=` `False` `     `  `    ``# fill the partition table in ` `    ``# bottom up manner ` `    ``for` `i ``in` `range``(``1``, ``sum` `/``/` `2` `+` `1``): ` `         `  `        ``for` `j ``in` `range``(``1``, n ``+` `1``): ` `            ``part[i][j] ``=` `part[i][j ``-` `1``] ` `             `  `            ``if` `i >``=` `arr[j ``-` `1``]: ` `                ``part[i][j] ``=` `(part[i][j] ``or`  `                              ``part[i ``-` `arr[j ``-` `1``]][j ``-` `1``]) ` `         `  `    ``return` `part[``sum` `/``/` `2``][n] ` `     `  `# Driver Code ` `arr ``=` `[``3``, ``1``, ``1``, ``2``, ``2``, ``1``] ` `n ``=` `len``(arr) ` `if` `findPartition(arr, n) ``=``=` `True``: ` `    ``print``(``"Can be divided into two"``,  ` `             ``"subsets of equal sum"``) ` `else``: ` `    ``print``(``"Can not be divided into "``, ` `          ``"two subsets of equal sum"``) ` ` `  `# This code is contributed  ` `# by mohit kumar 29 `

## C#

 `// A dynamic programming based C# program  ` `// for partition problem ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns true if arr[] can be partitioned  ` `    ``// in two subsets of equal sum, otherwise  ` `    ``// false ` `    ``static` `bool` `findPartition (``int` `[]arr, ``int` `n) ` `    ``{ ` `         `  `        ``int` `sum = 0; ` `        ``int` `i, j; ` ` `  `        ``// Caculcate sun of all elements ` `        ``for` `(i = 0; i < n; i++) ` `            ``sum += arr[i]; ` ` `  `        ``if` `(sum % 2 != 0) ` `            ``return` `false``; ` ` `  `        ``bool` `[, ]part=``new` `bool``[sum / 2 + 1, n + 1]; ` ` `  `        ``// initialize top row as true ` `        ``for` `(i = 0; i <= n; i++) ` `            ``part[0, i] = ``true``; ` ` `  `        ``// initialize leftmost column, except  ` `        ``// part[0][0], as 0 ` `        ``for` `(i = 1; i <= sum/2; i++) ` `            ``part[i, 0] = ``false``; ` ` `  `        ``// Fill the partition table in botton  ` `        ``// up manner ` `        ``for` `(i = 1; i <= sum/2; i++) ` `        ``{ ` `            ``for` `(j = 1; j <= n; j++) ` `            ``{ ` `                ``part[i, j] = part[i, j - 1]; ` `                ``if` `(i >= arr[j - 1]) ` `                    ``part[i, j] = part[i, j] || ` `                    ``part[i - arr[j - 1],j - 1]; ` `            ``} ` `        ``} ` ` `  `        ``/* // uncomment this part to print table ` `        ``for (i = 0; i <= sum/2; i++) ` `        ``{ ` `            ``for (j = 0; j <= n; j++) ` `                ``printf ("%4d", part[i][j]); ` `            ````printf(" "); ``` `        ``} */` ` `  `        ``return` `part[sum / 2, n]; ` `    ``} ` ` `  `    ``// Driver program to test above funtion ` `    ``public` `static` `void` `Main () ` `    ``{ ` `        ``int` `[]arr = {3, 1, 1, 2, 2,1}; ` `        ``int` `n = arr.Length; ` `         `  `        ``if` `(findPartition(arr, n) == ``true``) ` `            ``Console.Write(``"Can be divided"`  `                  ``+ ``" into two subsets of"` `                          ``+ ``" equal sum"``); ` `        ``else` `            ``Console.Write(``"Can not be "`  `               ``+ ``"divided into two subsets"` `                      ``+ ``" of equal sum"``); ` ` `  `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

Output:

`Can be divided into two subsets of equal sum`

Following diagram shows the values in partition table.

Time Complexity: O(sum*n)
Auxiliary Space: O(sum*n)
Please note that this solution will not be feasible for arrays with big sum.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}