The partition problem is a variation of the 01 knapsack problem. In this problem, we have to divide elements of the array into two sets such that they have equal sum. In this article, we provide a c++ solution with an explanation.
Partition Problem Description
Given an array of n integers. We have to divide the array elements into two such such that –
- Each element of the array is part of a single set.
- Sum of elements of both sets should be equal.
Determine whether it is possible or not.
- First line contains an integer n – the number of integers.
- Next line contains n integers – the elements of an array.
- Single line output Yes if possible otherwise No.
Partition Problem Solution
This problem is variation of 0-1 Knapsack. To understand better we can rephrase question as find if we can pick some elements of the array such that sum of the picked elements is equal to S ( Here S = (Sum of all elements)/2 ).
The problem has the same exact solution as the 0-1 knapsack problem with some miner changes. Refer to code below.
The Two sets are 2,5 & 1,1,2,3
Sum of each set is 7.