Java递归问题

我在Java中遇到了一个递归面试问题，需要你的帮助。

Write a **Java function**这样 :: 给定一个 int 数组，是否可以将 int 分为两组，使两组之和相同，并具有以下约束：所有 5 的倍数的值必须在一组中，并且所有是 3 的倍数（而不是 5 的倍数）的值都必须在另一个中。 （不需要循环。）

split53({1,1}) → true
split53({1, 1, 1}) → false
split53({2, 4, 2}) → true

PS：这是惠普的面试题

这个问题可以很容易地简化为以下内容：给定一组整数numbers和一个整数target，是否有可能找到一个子集numbers总和等于target?
如果过渡需要澄清，请告诉我。

可以用以下方法解决DP http://en.wikipedia.org/wiki/Dynamic_programming in O(numbers.size * target)时间。想法如下

1. When numbers.size is 0，唯一可达到的总和是0.
2. 假设我们有numbers == {1, 3}，在这种情况下求和{0, 1, 3, 4}可用。如果我们添加另一个元素会怎样numbers, 4？现在，所有旧的金额仍然可以达到，也可以达到一些新的金额：{0 + 4, 1 + 4, 3 + 4, 4 + 4}。因此，对于numbers == {1, 3, 4}，可用金额为{0, 1, 3, 4, 5, 7, 8}.
3. 以这种方式，逐个添加，您可以构建可达总和的列表。

一个工作示例（它不处理负数，但您可以轻松修复该问题）

boolean splittable(int[] numbers, int target) {
    boolean[] reached = new boolean[target + 1];
    reached[0] = true;

    for (int number : numbers) {
        for (int sum = target - 1; sum >= 0; --sum) {
            if (reached[sum] && sum + number <= target) {
                reached[sum + number] = true;
            }
        }
    }

    return reached[target];
}

Run it

System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true
System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false

edit
我刚刚注意到要求的“递归”部分。那么，DP 可以重写为递归：记忆化 http://en.wikipedia.org/wiki/Memoization，如果这是硬性要求。这将保留运行时的复杂性。

edit 2
论团体。您必须将可被 3 或 5 整除的元素分配给相应的组before您继续执行该算法。比方说，所有元素的总和是s，能被 3 整除的元素之和为s3能被 5 但不能被 3 整除的元素之和为s5。在这种情况下，在分配了这些“特殊”元素后，您必须拆分一组中的总和为s/2 - s3并在另一个s/2 - s5.