Java算法 将整型数组分组，使两组中各元素加起来的和相等

Question

将整型数组分组，使两组中各元素加起来的和相等，求分组方法有多少种。如：数组{1,1,1,1,2,2}有a组（{1,1,1,1}）、b组（{2,2}）；a组（{1,1,2}）、b组（{1,1,2}）；a组（{2,2}）、b组（{1,1,1,1}）三种分组方法。求算法思路。

Answer 1

我觉得是这样，因为分成两组且和相等，那么和一定是sum/2，这里可以有个特判是否无解。

然后问题成了有多少组合和为sum/2的动态规划

dp(i,j) = dp(i-1,j-a(i))+dp(i-1,j)

解释为前i个元素和为j的组合有多少种

答案应该要/2

不知道对不对，感觉没问题，爪机码字欢迎指教。

Answer 2

一共就两组，把所有可能分组列举出来再排出不就完了。