劃分整數2甚至總和

Question

我很難解決這個編程問題。我需要從2 <= N <= 30的任意位置獲取大小爲N的整數。我需要將數組分成兩個較小的數組，它們的總和相等，如果它們不相等，則它們需要儘可能接近相同的值。我猜想在這種情況下使用某種遞歸函數是理想的，但如果不是這樣的話，動態編程的解決方案也會起作用。

Answer 1

我想你可以查看wikipedia article on Partition problem。它提供了在C＃僞多項式算法的僞代碼，你可以比較容易地轉換成C++：

public static bool BalancePartition(int[] S) 
{ 
    int n = S.Length; 
    int N = S.Sum(); 
    bool[,] P = new bool[N/2 + 1, n + 1]; 

    for (int i = 0; i < n + 1; i++) 
     P[0, i] = true; 

    for (int i = 1; i <= N/2; i++) 
     for (int j = 1; j <= n; j++) 
      if (S[j - 1] <= i) 
       P[i, j] = P[i, j - 1] || P[i - S[j - 1], j - 1]; 
      else 
       P[i, j] = P[i, j - 1]; 

    return P[N/2, n]; 
}