c++ - 将一组数字拆分为成员子组

Question

我想问一下如何检查一组数字是否可以分成子组(每个子组必须有 3 个成员)，并且每个子组成员的总和都相等。这么多组合怎么查？

示例:

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

可以分为

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

Answer 1

可以遵循递归方法，其中一个保留两个数组:

• 包含每个子组总和的数组。
• 一个 bool 数组，用于检查元素是否已被纳入一些子组或不。

您要求 3 个子组，即本文其余部分中的 K = 3，但请记住，在处理递归时，应考虑基本情况。在这种情况下，我们将关注两个基本情况:

1. 如果K为1，那么我们已经有了答案，完整的数组只有具有相同总和的子集。
2. 如果 N < K，则不可能将数组分成子集等和，因为我们不能将数组分成超过 N 个部分。

如果组的和不能被K整除，那么就不可能将它整除。只有当 k 除和时，我们才会继续。我们的目标减少了将组划分为 K 个子组，其中每个子组的总和应该是该组的总和除以 K。

在下面的代码中，编写了一个递归方法，它试图将数组元素添加到某个子集中。如果这个子集的总和达到要求的总和，我们递归地迭代下一部分，否则我们回溯不同的元素集。如果总和达到所需总和的子集数为(K-1)，我们标记可以将数组划分为总和相等的 K 个部分，因为剩余元素的总和已等于所需总和。

引自here ，而在您的情况下，您将设置 K = 3，如示例代码中所示。

// 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";
}

输出:

Partitions into equal sum is possible.

---

相关链接:2和 3 .