Question

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.

Answer 1

HELLO ,

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])

// A recursive C++ program for partition problem

IHOPE THIS ANSWER CAN HELP YOU ....!!