Set-Partition Problem

The set partitioning problem involves partitioning a set into disjoint subsets that cover all elements of the original set. It has applications in scheduling and manufacturing.

Some examples algorithms are:

  • Dynamic programming
  • Backtracking
  • Branch and bound

Java - Dynamic programming:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

boolean partition(Set<Integer> set) {
  int n = set.size();
  boolean[][] dp = new boolean[n+1][1<<n];

  // Base cases
  dp[0][0] = true;

  // Build partition  
  for (int i = 1; i <= n; i++) {
    for (int mask = 0; mask < (1<<n); mask++) {
      // Try including/excluding element
    }
  }

  return dp[n][(1<<n)-1]; // Full partition exists?
}

C++ - Backtracking:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

bool partition(unordered_set<int> set) {

  vector<int> currPartition;
  return solve(0, currPartition, set);
  
}

bool solve(int i, vector<int>& curr, unordered_set<int>& remaining) {
  if (remaining.empty()) {
    return true; // Full partition exists
  }

  // Try including/excluding element i 
  return false; // No valid partition
}

Python - Branch and bound:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def partition(elements):

  minCost = float("inf")
  
  def backtrack(currPartition):
    # Try partitions    
    if cost(currPartition) >= minCost:
      # Prune branch  
      return

    if validPartition(currPartition):
      global minCost 
      minCost = cost(currPartition)  

  backtrack([])

  return minCost != float("inf") # Solution found

Set partitioning provides an abstraction for allocation and splitting problems involving sets.

The set partition problem is a classic problem in computer science. Given a set of positive integers, the goal is to find a way to partition the set into subsets whose sums are all equal. The problem can be solved in polynomial time using dynamic programming. The idea is to build up a table of solutions, one for each possible sum. The table is initialized with the all-zero solution. Then, we iterate over the set of positive integers, and for each integer (x), we update the table by adding the solution for (x) to the solutions for all sums that are (x) greater. At the end of the iteration, the table will contain the solution for the original set. The time complexity of this algorithm is (O(nS)), where (n) is the number of elements in the set and (S) is the sum of the elements.

The Set-Partition problem asks whether a given set of integers can be partitioned into two subsets such that the sum of the numbers in both subsets is the same. This problem is a classic example in computer science and is known to be NP-complete.

In simple terms, given a set of integers, can you divide it into two sets so that the sum of the numbers in each set is equal?

Example Code in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class SetPartition {
    public static boolean canPartition(int[] nums, int index, int sum1, int sum2) {
        if (index == nums.length) {
            return sum1 == sum2;
        }

        return canPartition(nums, index + 1, sum1 + nums[index], sum2) ||
               canPartition(nums, index + 1, sum1, sum2 + nums[index]);
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums, 0, 0, 0));  // Output: true
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>

bool canPartition(int nums[], int index, int sum1, int sum2, int size) {
    if (index == size) {
        return sum1 == sum2;
    }

    return canPartition(nums, index + 1, sum1 + nums[index], sum2, size) ||
           canPartition(nums, index + 1, sum1, sum2 + nums[index], size);
}

int main() {
    int nums[] = {1, 5, 11, 5};
    std::cout << canPartition(nums, 0, 0, 0, 4) << std::endl;  // Output: 1 (true)
    return 0;
}

Example Code in Python

1
2
3
4
5
6
7
8
9

def can_partition(nums, index, sum1, sum2):
    if index == len(nums):
        return sum1 == sum2

    return can_partition(nums, index + 1, sum1 + nums[index], sum2) or \
           can_partition(nums, index + 1, sum1, sum2 + nums[index])

nums = [1, 5, 11, 5]
print(can_partition(nums, 0, 0, 0))  # Output: True

In all three implementations, we recursively explore both options for each number: putting it in the first set or the second set. We return true if we find a valid partition.