c# - 我可以将数组分成多少次，总和相等？

Question

我想找到可以将数组划分为 2 个非空部分的次数，使得左侧分区中元素的总和等于右侧分区中元素的总和。

每次成功分区后，我们丢弃左分区或右分区，并使用剩余分区作为数组继续播放。

最初，有一个数组，a , 包含 N 个整数。 N <= 2^14

static int Compute(int[] a, int arraySize)
{
     return ComputeNumberOfPartition(a.ToList(), arraySize,  0);
}

static int ComputeNumberOfPartition(List<int> a, int N, int points)
{
     List<int> left = new List<int>();
     List<int> right = new List<int>();

     for (int i = 0; i < N; ++i)
     {
         if (sum(left) <= sum(right)) { left.Add(a[i]);  }
         else                         { right.Add(a[i]); }
     }

     if (sum(left) == sum(right))
     {
         return left.Count >= right.Count ? 
                ComputeNumberOfPartition(left, left.Count, ++points) :
                ComputeNumberOfPartition(right, right.Count, ++points);
     }

     return points;
}

static int sum(List<int> a)
{
     int sum = 0;
     for (int i = 0; i < a.Count; ++i)
     {
         sum += a[i];
     }

     return sum;
}

例如:

input1 3 3 3

output1 0

我们不能将两个部分分成总和相等的部分。因此，她的最大可能得分为 0。

input2 4 1 0 1 1 0 1

output2 3

我的解决方案非常慢。我们怎样才能更有效地解决它？这个问题来自hackerrank

Answer 1

public Tuple<int[], int[]> SplitIntArray(int[] array, int index) {
    return new Tuple<int[], int[]>(
        array.Take(index).ToArray(),
        array.Skip(index).ToArray()
    );
}
public string AggregateSumString(int[] array) {
    return array.Select(i => i.ToString()).Aggregate((sumString, next) => 
        String.IsNullOrEmpty(sumString) ? next : String.Format("{0} + {1}", sumString, next))
}

然后，

int[] array;
var results = new List<Tuple<int[], int[]>>();

for (int i = 0; i < array.Length; i++) {
    var tuple = SplitIntArray(array, i);

    if (tuple.Item1.Sum() == tuple.Item2.Sum()) {
        results.Add(tuple);
    }            
}

// results contains all pairs of arrays that sum to the same value.
foreach (var tuple in results) {
    Console.WriteLine(
        String.Format("{0} == {1}", AggregateSumString(tuple.Item1), AggregateSumString(tuple.Item2)));
}