Algorithms for Coding Interviews in C++/

...

/

Solution: The Partition Problem

Solution: The Partition Problem

This review provides a detailed analysis of the ways to solve the partition problem

We'll cover the following...

Solution #1: Brute Force

C++
#include <iostream>
using namespace std;
bool canPartitionRecursive(int num[], int n, int sum, int currentIndex) {
  // base check
  if (sum == 0)
    return true;
  if (n == 0 || currentIndex >= n)
    return false;
  // recursive call after choosing the number at the currentIndex
  // if the number at currentIndex exceeds the sum, we shouldn't process this
  if (num[currentIndex] <= sum) {
    if (canPartitionRecursive(num, n, sum - num[currentIndex], currentIndex + 1))
      return true;
  }
  // recursive call after excluding the number at the currentIndex
  return canPartitionRecursive(num, n, sum, currentIndex + 1);
}
bool canPartition(int num[], int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += num[i];
  // if 'sum' is an odd number, we can't have two subsets with equal sum
  if (sum % 2 != 0)
    return false;
  return canPartitionRecursive(num, n, sum / 2, 0);
}
int main() {
    int set1[] = {1, 2, 3, 4};
    cout << canPartition(set1, 4) << endl;
    int set2[] = {1, 1, 3, 4, 7};
    cout << canPartition(set2, 5) << endl;
    int set3[] = {2, 3, 4, 6};
    cout << canPartition(set3, 4) << endl;
}

This problem is very similar to the 0/1 knapsack. It essentially follows the same pattern. This solution tries all the combinations of partitioning the given numbers into two sets to see if any pair of sets has an equal sum.

If S represents the total sum of all the given numbers, then the two equal subsets must have a sum equal to S/2. So our problem is technically to find a subset of the given numbers that has a total sum of S/2.

Pseudocode

for each number 'i' 
  create a new set which INCLUDES number 'i' if it does not exceed 'S/2', and recursively 
      process the remaining numbers
  create a new set WITHOUT number 'i', and recursively process the remaining items 
return true if any of the above sets have a sum equal to 'S/2', otherwise, return false

Time Complexity

The time complexity of the above algorithm is exponential O(2n)O(2^n) ...