Dividing an array into K subsets such that sum of all subsets is same using bitmasks+DP

Question

So, this problem I dont have any clue how to solve it the problem statement is :

Given a set S of N integers the task is decide if it is possible to divide them into K non-empty subsets such that the sum of elements in every of the K subsets is equal.

N can be at max 20. K can be at max 8

The problem is to be solved specifically using DP+Bitmasks!

I cannot understand where to start ! As there are K sets to be maintained , I cannot take K states each representing some or the other!!

If I try taking the whole set as a state and K as the other, I have issues in creating a recurrent relation!

Can you help??

The link to original problem Problem

Answer 1

You can solve the problem in O(N * 2^N), so the K is meaningless for the complexity.

First let me warn you about the corner case N < K with all the numbers being zero, in which the answer is "no".

The idea of my algorithm is the following. Assume we have computed the sum of each of the masks (that can be done in O(2^N)). We know that for each of the groups, the sum should be the total sum divided by K.

We can do a DP with masks in which the state is just a binary mask telling which numbers have been used. The key idea in removing the K from the algorithm complexity is noticing that if we know which numbers have been used, we know the sum so far, so we also know which group we are filling now (current sum / group sum). Then just try to select the next number for the group: it will be valid if we do not exceed the group expected sum.

You can check my C++ code:

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;

ll v[21 + 5];
ll sum[(1 << 21) + 5];
ll group_sum;
int n, k;

void compute_sums(int position, ll current_sum, int mask)
{
    if (position == -1)
    {
        sum[mask] = current_sum;
        return;
    }

    compute_sums(position - 1, current_sum, mask << 1);
    compute_sums(position - 1, current_sum + v[position], (mask << 1) + 1);
}

void solve_case()
{
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
        cin >> v[i];

    memset(sum, 0, sizeof(sum));
    compute_sums(n - 1, 0, 0);

    group_sum = sum[(1 << n) - 1];
    if (group_sum % k != 0)
    {
        cout << "no" << endl;
        return;
    }
    if (group_sum == 0)
    {
        if (n >= k)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
        return;
    }

    group_sum /= k;

    vector<int> M(1 << n, 0);
    M[0] = 1;
    for (int mask = 0; mask < (1 << n); ++mask)
    {
        if (M[mask])
        {
            int current_group = sum[mask] / group_sum;
            for (int i = 0; i < n; ++i)
            {
                if ((mask >> i) & 1)
                    continue;
                if (sum[mask | (1 << i)] <= group_sum * (current_group + 1))
                    M[mask | (1 << i)] = 1;
            }
        }
    }
    if (M[(1 << n) - 1])
        cout << "yes" << endl;
    else
        cout << "no" << endl;
}

int main()
{
    int cases;
    cin >> cases;
    for (int z = 1; z <= cases; ++z)
        solve_case();
}

Answer 2

Here's the working O(K*2^N*N) implementation in JavaScript. From the pseudo code https://discuss.codechef.com/questions/58420/sanskar-editorial

http://jsfiddle.net/d7q4o0nj/

function equality(set, size, count) {
    if(size < count) { return false; }
    var total = set.reduce(function(p, c) { return p + c; }, 0);
    if((total % count) !== 0) { return false }
    var subsetTotal = total / count;
    var search = {0: true};
    var nextSearch = {};
    for(var i=0; i<count; i++) {
        for(var bits=0; bits < (1 << size); bits++){
            if(search[bits] !== true) { continue; }
            var sum = 0;
            for(var j=0; j < size; j++) {
                if((bits & (1 << j)) !== 0) { sum += set[j]; }
            }
            sum -= i * subsetTotal;
            for(var j=0; j < size; j++) {
                if((bits & (1 << j)) !== 0) { continue; }
                var testBits = bits | (1 << j);
                var tmpTotal = sum + set[j];
                if(tmpTotal == subsetTotal) { nextSearch[testBits] = true; }
                else if(tmpTotal < subsetTotal) { search[testBits] = true; }
            }            
        }
        search = nextSearch;
        nextSearch = {};
    }
    if(search[(1 << size) - 1] === true) {
        return true;
    }
    return false;
}

console.log(true, equality([1,2,3,1,2,3], 6, 2));
console.log(true, equality([1, 2, 4, 5, 6], 5, 3));
console.log(true, equality([10,20,10,20,10,20,10,20,10,20], 10, 5));
console.log(false, equality([1,2,4,5,7], 5, 3));

EDIT The algorithm finds all of the bitmasks (which represent subsets bits) that meet the criteria (having a sum tmpTotal less than or equal to the ideal subset sum subsetTotal). Repeating this process by the amount of subsets required count, you either have a bitmask where all size bits are set which means success or the test fails.

EXAMPLE

set = [1, 2, 1, 2]

size = 4

count = 2, we want to try to partition the set into 2 subsets

subsetTotal = (1+2+1+2) / 2 = 3

Iteration 1:

search = {0b: true, 1b: true, 10b: true, 100b: true, 1000b: true, 101b: true}

nextSearch = {11b: true, 1100b: true, 110b: true, 1001b: true }

Iteration 2:

search = {11b: true, 1100b: true, 110b: true, 1001b: true, 111b: true, 1101b: true }

nextSearch = {1111b: true}

Final Check

(1 << size) == 10000b, (1 << size) - 1 == 1111b

Since nextSearch[ 1111b ] exists we return success.