将一组数字拆分成一个子组成员

Question

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

实施例：

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

可分为

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

Answer 1

甲递归方法可以遵循，其中一个保持两个阵列：

• 与总和的阵列每个小组。
• 一个布尔数组，用于检查某个元素是否已被纳入 某个子组中。

您要求提供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"; 
} 

输出：

分区分成相等的总和是可能的。

---

相关链接：2和3。

Answer 2

你可能只是做这样的事情，在这种特殊情况下（3×3）：

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

如果您有更长的阵列（3+ * 3），那么你可以使用复发（你可以在我的例子中使用它太），但那仍然是非常缓慢的。