Partition Problems Brute Force Algorithm

Question

I am trying to do the pseudocode for the partition problem below in bruteforce.

a set of integers X and an integer k (k >1). Find k subsets of X such that the numbers in each subset sum to the same amount and no two subsets have an element in common, or conclude that no such k subsets exist. The problem is NP-Complete

For example, with X = {2, 5, 4, 9, 1, 7, 6, 8} and k = 3, a possible solution would be: {2, 5, 7}, {4, 9, 1}, {6, 8} because all of them sum up to 14.

for exhaustive search I know typically we would have to search every possible solution and see if the target is similar. But as this is partition problem this could be tricky.

The algorithm brute force :

Subset= X.sum/K //I had a guess this would make the parition
For int i==1; I <subset; i++ // this would change partition if not found in the first one
If (j=0; I<n; i++)
    Sum == s[i]
    If sum == target 
        Display “found”
    Else 
    “not found”

Answer 1

I will start with the comment provided by @m69. Since you know that all elements must be used then you know that the total sum of your partitions will be equal to the total sum of the whole set. Adding in the knowledge that each partition has the same sum then you can determine for k partitions each will need to have a sum of totalSum / k. This provides a quick way to detect many sets that cannot be partitioned into k subsets. This code might look something like this:

if (totalSum % k != 0)
{
    /* The set can't be partitioned into k elements */
}

Now it's time to start building some partitions. I recommend using a recursive solution. So we will start with a function that takes an array and the sum that each partition of that array is supposed to have.

check_partition(array, partitionSum)
{
    /* code goes here */
}

There will be two base cases for our recursion. The first is that if the array given has a total sum equal to the partition sum then our partitioning is successful. In this case we will return the array.

arraySum = sum(array);
if (sum(array) == partitionSum)
{
    return array;
}

The other base case is if the sum of the array is less than the target sum of the partition then this attempt has failed. In this case we return null to indicate that the given partition does not work.

if (sum(array) < partitionSum)
{
    return null;
}

Now to write the recursive step. For this step we want to pick an element from the array and build every partition that sums to the target which includes this number. The largest element in the array is the best element to do this with as it will have the fewest possible partitions. Then for each partition in that set we want to remove the elements in it from the larger array and then run the function again with that smaller array.

maxElementPartitions = buildAllMaxElementPartitions(array, partitionSum);
foreach(partition in maxElementPartitions)
{
    arrayWithoutPartition = removePartition(array, partition)
    resultSet = check_partition(arrayWithoutPartition, partitionSum);
    if (resultSet == null)
    {
        /* It failed down the chain of recursion somewhere */
        /* Move to the next iteration of the loop */
    }
    else
    {
        return = resultSet + partition;
    }
}
/* If the loop exits no results were found */
return null;

This recursive function will return a successful partiton, or if none exists it will return null.

Answer 2

Here is an example in JavaScript that asssumes positive array elements. The algorithm pops the stack and outputs the result if it is valid by checking the count of completed parts; otherwise, it takes each array element in turn and adds another set of parameters to the stack, one where the array element is the first addition to an empty part, and one where it's added in turn to each of the parts yet filled. (For convenience, result accrues as a string where the part index precedes each array element.)

var arr = [2,5,4,9,1,7,6,8]
var k = 3;

var n = arr.length;
var target = arr.reduce( (prev, curr) => prev + curr ) / k;
var sums = [];
for (var i=0; i<k; i++){
  sums[i] = 0;
}

var stack = [[0,sums,0,""]];

while (stack[0] !== undefined){
  var params = stack.pop();

  var i = params[0];
  var sums = params[1];
  var done = params[2];
  var result = params[3];

  if (done == k){
    console.log(result);
    continue;
  } else if (i == n){
    continue;
  }

  var was_first_element = false;

  for (var j=0; j<k; j++){
    if (!was_first_element && sums[j] == 0){
      was_first_element = true;
      var _sums = sums.slice();
      _sums[j] += arr[i];
      stack.push([i + 1,_sums,done + (_sums[j] == target ? 1 : 0),result + j + ": " + arr[i] +", "]);
    } else if (sums[j] != 0 && arr[i] + sums[j] < target && i < n - 1){
      var _sums = sums.slice();
      _sums[j] += arr[i];
      stack.push([i + 1,_sums,done,result + j + ": " + arr[i] +", "]);
    } else if (sums[j] != 0 && arr[i] + sums[j] == target){
      var _sums = sums.slice();
      _sums[j] += arr[i];
      stack.push([i + 1,_sums,done + 1,result + j + ": " + arr[i] +", "]);
    }
  }
}

Output:

/*
0: 2, 1: 5, 0: 4, 1: 9, 2: 1, 2: 7, 2: 6, 0: 8
{2,4,8} {5,9} {1,7,6}

0: 2, 1: 5, 0: 4, 1: 9, 0: 1, 0: 7, 2: 6, 2: 8
{2,4,1,7} {5,9} {6,8}

0: 2, 0: 5, 1: 4, 1: 9, 1: 1, 0: 7, 2: 6, 2: 8
{2,5,7} {4,9,1} {6,8}
*/