给定一个数组,元素可重复,要求分成两个数组,使得这两个数组之和的差值最小。

例如:1 2 3 4 5 6那么分成:1 2 3 5 和 4 6,差值为1。输出和值较大的集合在原数组的下标。

思路:

设原数组之和为sum,两个集合之和分别为A和B, half = sum/2。

假设A <= half(两数组之和要么一大一小,要么相等),那么就有:

A + B = sum

|half - A| = |B - half| = |(B - A)/2|

接下来只要去寻找大于等于half的数,且能由原数组组成的数中最小的数,即为答案。
使用DFS搜索可行解。