划分整数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]; 
}