Splitting a group of numbers into a subgroups of members

Question

I wanted to ask how to check if a group of numbers could be split into subgroups (every subgroup has to have 3 members) that every sum of subgroups' members would be equal. How to check so many combinations?

Example:

int numbers[] = {1, 2, 5, 6, 8, 3, 2, 4, 5};

can be divided into

{1, 5, 6}, {2, 8, 2}, {3, 4, 5}

Answer 1

A recursive approach can be followed, where one keeps two arrays:

• An array with the sums of every subgroup.
• A boolean array to check whether an element is already taken into some subgroup or not.

You asked for 3 subgroups, i.e. K = 3 in the rest of this post, but keep in mind that when dealing with recursion, bases cases should be taken into account. In this case we will focus on two base cases:

1. If K is 1, then we already have our answer, complete array is only subset with same sum.
2. If N < K, then it is not possible to divide array into subsets with equal sum, because we can’t divide the array into more than N parts.

If the sum of group is not divisible by K, then it is not possible to divide it. We will only proceed if k divides sum. Our goal reduces to divide the group into K subgroups where sum of each subgroup should be the sum of the group divided by K.

In the code below a recursive method is written which tries to add array element into some subset. If sum of this subset reaches required sum, we iterate for next part recursively, otherwise we backtrack for different set of elements. If number of subsets whose sum reaches the required sum is (K-1), we flag that it is possible to partition array into K parts with equal sum, because remaining elements already have a sum equal to required sum.

Quoted from here, while in your case you would set K = 3, as in the example code.

// C++ program to check whether an array can be
// subsetitioned into K subsets of equal sum
#include <bits/stdc++.h>
using namespace std;

// Recursive Utility method to check K equal sum
// subsetition of array
/**
    array           - given input array
    subsetSum array   - sum to store each subset of the array
    taken           - boolean array to check whether element
                      is taken into sum subsetition or not
    K               - number of subsetitions needed
    N               - total number of element in array
    curIdx          - current subsetSum index
    limitIdx        - lastIdx from where array element should
                      be taken */
bool isKPartitionPossibleRec(int arr[], int subsetSum[], bool taken[],
                   int subset, int K, int N, int curIdx, int limitIdx)
{
    if (subsetSum[curIdx] == subset)
    {
        /*  current index (K - 2) represents (K - 1) subsets of equal
            sum last subsetition will already remain with sum 'subset'*/
        if (curIdx == K - 2)
            return true;

        //  recursive call for next subsetition
        return isKPartitionPossibleRec(arr, subsetSum, taken, subset,
                                            K, N, curIdx + 1, N - 1);
    }

    //  start from limitIdx and include elements into current subsetition
    for (int i = limitIdx; i >= 0; i--)
    {
        //  if already taken, continue
        if (taken[i])
            continue;
        int tmp = subsetSum[curIdx] + arr[i];

        // if temp is less than subset then only include the element
        // and call recursively
        if (tmp <= subset)
        {
            //  mark the element and include into current subsetition sum
            taken[i] = true;
            subsetSum[curIdx] += arr[i];
            bool nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
                                            subset, K, N, curIdx, i - 1);

            // after recursive call unmark the element and remove from
            // subsetition sum
            taken[i] = false;
            subsetSum[curIdx] -= arr[i];
            if (nxt)
                return true;
        }
    }
    return false;
}

//  Method returns true if arr can be subsetitioned into K subsets
// with equal sum
bool isKPartitionPossible(int arr[], int N, int K)
{
    //  If K is 1, then complete array will be our answer
    if (K == 1)
        return true;

    //  If total number of subsetitions are more than N, then
    // division is not possible
    if (N < K)
        return false;

    // if array sum is not divisible by K then we can't divide
    // array into K subsetitions
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];
    if (sum % K != 0)
        return false;

    //  the sum of each subset should be subset (= sum / K)
    int subset = sum / K;
    int subsetSum[K];
    bool taken[N];

    //  Initialize sum of each subset from 0
    for (int i = 0; i < K; i++)
        subsetSum[i] = 0;

    //  mark all elements as not taken
    for (int i = 0; i < N; i++)
        taken[i] = false;

    // initialize first subsubset sum as last element of
    // array and mark that as taken
    subsetSum[0] = arr[N - 1];
    taken[N - 1] = true;
    if (subset < subsetSum[0])
        return false;

    //  call recursive method to check K-subsetition condition
    return isKPartitionPossibleRec(arr, subsetSum, taken,
                                     subset, K, N, 0, N - 1);
}

//  Driver code to test above methods
int main()
{
    int arr[] = {2, 1, 4, 5, 3, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;

    if (isKPartitionPossible(arr, N, K))
        cout << "Partitions into equal sum is possible.\n";
    else
        cout << "Partitions into equal sum is not possible.\n";
}

Output:

Partitions into equal sum is possible.

---

Relevant links: 2 and 3.

Answer 2

You could just do something like that in this particular case (3x3):

const int COUNT = 9;
bool test(int const (&array)[COUNT], std::vector<std::vector<int>>* result) {

    for(int _1=0; _1<COUNT-2; ++_1) {
        for(int _2=1; _2<COUNT-1; ++_2) {
            if(_2 == _1)
                continue;
            for(int _3=2; _3<COUNT; ++_3) {
                if(_3 == _2 || _3 == _1)
                    continue;
                std::vector<int> chosen1 {array[_1], array[_2], array[_3]};
                std::vector<int> rest;
                for(int _x = 0; _x < COUNT; ++_x) {
                    if(_x != _1 && _x != _2 && _x != _3) {
                        rest.push_back(array[_x]);
                    }
                }

                for (int _4 = 0; _4 < COUNT-5; ++_4) {
                    for (int _5 = 1; _5 < COUNT-4; ++_5) {
                        if(_5 == _4)
                            continue;
                        for (int _6 = 2; _6 < COUNT-3; ++_6) {
                            if(_6 == _5 || _6 == _4)
                                continue;
                            std::vector<int> chosen2 = {rest[_4], rest[_5], rest[_6]};
                            std::vector<int> chosen3;
                            for(int _x = 0; _x < COUNT-3; ++_x) {
                                if(_x != _4 && _x != _5 && _x != _6) {
                                    chosen3.push_back(rest[_x]);
                                }
                            }

                            int total = std::accumulate(chosen1.begin(), chosen1.end(), 0);

                            if((std::accumulate(chosen2.begin(), chosen2.end(), 0) == total) &&
                               (std::accumulate(chosen3.begin(), chosen3.end(), 0) == total)) {
                                *result = {chosen1, chosen2, chosen3};
                                return true;
                            }
                        }
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    int values[] = {1, 2, 5, 6, 8, 3, 2, 4, 5};
    std::vector<std::vector<int>> result;
    if(test(values, &result)) {
        for(auto& x : result) {
            std::cout << "{";
            for(auto& y : x) {
                std::cout << y << ",";
            }
            std::cout << "}";
        }
        std::cout << std::endl;
    } else {
        std::cout << "not found";
    }
}

If you had longer array (3+ * 3) then you could use recurrence (you could use it in my example too), but that would be still very slow.