將一組數字拆分成一個子組成員

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），那麼你可以使用復發（你可以在我的例子中使用它太），但那仍然是非常緩慢的。