# Partition Problem (Recursive Approach)

**You are given a set of numbers and asked to determine whether given set can be partitioned into subsets such that sum of element in both subsets is same.**** To Solve this problem**

Lets understand the problem statement once again with the help of examples

**Example 1**

S[] = {2,1,5,4}

Output = TRUE

The set can be partitioned as {2,4} & {1,5}

**Example 2**

S[] = {1,2,3,1}

Output = FALSE

Because we can’t separate above set in two having equal sum.

**Key Observation and steps**

- Calculate sum of array. If it comes out to be odd we can’t separate that set into two.
- If sum of array is even, then we need to find a subset having sum equal to sum/2.

Now we can return false simply for very first step and can use Recursive approach and Dynamic Programming. Here we will discuss Recursive approach for better understanding, another approach is discussed here (LINK).

For the following code we define
isSubsetFound(a, n, sum/2) * *be the function that return
true if there is a subset of
a[0 to n-1] with sum equal to
sum/2

#include<bits/stdc++.h> using namespace std; bool isSubsetFound(int a[], int n,int sum) { if(sum == 0) // At this stage we found a subset having sum equal to sum/2 return true; if(n == 0 && sum!=0) // Return false when no subset is obtained using n elements having sum equal to sum/2 return false; if(a[n-1]>sum) // Ignore last element if it greater than sum. return isSubsetFound(a, n-1, sum); // Check if a subset exists by excluding an element or by including an element. return isSubsetFound(a, n-1, sum) || isSubsetFound(a, n-1, sum - a[n-1]); } bool driver(int a[], int n) { int sum=0; for(int i=0;i<n;i++) sum+=a[i]; if(sum%2) // If sum is odd we cant find a subset. return false; return isSubsetFound(a,n,sum/2); } int main() { int a[10000]={1,2,3,4},n=4; driver(a,n)?cout<<"True":cout<<"False"; return 0; }

**Time Complexity:**

In worst case, we try to find two possibilities in above approach whether to include or exclude an element for each element therefore time complexity is \(O(2^n)\) .

This article is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.