java - 使用递归将偶数分解为 2,4,6 的和

Question

我必须用Java编写一个递归方法，使用递归将偶数分成2,4,6的和，同时不能有2个相同的数字连续出现。

例如n=8返回:

([2,4,2], [2,6], [6,2])

(where [2,2,2,2], [2,2,4], [4,2,2], [4,4] are not allowed as answers)

我正在寻找执行此操作的算法。目前我想我需要给该方法提供两个参数，其中一个是 int n及其他ArrayList<Integer>存储找到的分离方式。但我很难想到可以做到这一点的算法。

public static ArrayList<Integer> subtractions(int n, ArrayList<Integer> integers){
    int sum = 0;
    for(Integer i:integers){
        sum += i;
    }
    if(n>2 && sum<n) {
        integers.add(n - 2);
        return subtractions(n - 2, integers);
    }
    integers.add(2);
    return integers;
}

这就是我现在所拥有的，但在 n=8 的情况下它只给了我一个答案那就是[6,2]

有人可以给我一个起始位置或其他东西吗？

Answer 1

您忽略了整个复杂性。您不应该处理整数列表，而应该处理整数列表的列表。这个问题更多的是关于数据结构而不是数学。我的示例解决方案:

public static List<List<Integer>> subtractions_recursive(int target, int exclude) {

    List<List<Integer>> solutions = new ArrayList<>();

    if (target == 0) { // base case for recursion
        List<Integer> empty = new ArrayList<>(); // ()
        solutions.add(empty); // (())
    } else {
        for (int i = 2; i <= 6 && target - i > -1; i += 2) {
            if (i == exclude) {
                continue;
            }

            List<List<Integer>> sub_solutions = subtractions_recursive(target - i, i); // ((4, 2), (6))

            for (List<Integer> sub_solution:sub_solutions) {
                sub_solution.add(0, i); // ((2, 4, 2), (2, 6))
            }

            solutions.addAll(sub_solutions);
        }
    }

    return solutions; // ((2, 4, 2), (2, 6), (6, 2))
}

public static List<List<Integer>> subtractions(int target) {
    return subtractions_recursive(target, 0);
}