贝壳，java，笔试最后一题怎么做？
题目是这样的：给定一个数组，将其分为两部分，A和B，要求A的和与B的和相差最小；在这个前提下，让A包含的个数与B包含的个数相差尽可能大。
输出：这两部分的和之差 以及 个数之差。
示例：输入 1 2 3 4 5 6， 输出：1,2 （和相差1， 个数相差2， 比如：1 2 3 4， 5 6）
我测试用例能过，但是会超时，最后过了36%
思路是：
两部分中一定有一部分小于等于sum/2 ， 这部分越大越好。所以先算这部分最大能有多大。
于是用动态规划，dp[a][b], 代表前a个中取一些数，和为b的可能性，一直遍历到b <= sum/2
小的那部分和应该为多少。
假设这一步得到的结果是A
接下来问题就变成了从数组中找和为A的子序列，这些子序列中个数最多和最少的。
然后我用的回溯法，我感觉就是这个回溯法超时了，但是不知道该怎么整了。
#贝壳找房##笔试题目#
投递传音控股等公司8个岗位 >