java - 生成总和为 N 的所有数字排列

Question

我正在编写一个程序来创建所有数字 <=N 的递归排列，加起来等于给定数字 N。但是我不知道如何创建该排列。任何见解将不胜感激。

起初，我尝试使用分区函数对数字进行分区，然后对每个数字集进行排列，但是我认为这行不通，最好的方法是递归排列，同时对数字求和，这超出了我的能力范围.

抱歉，如果这听起来真的很愚蠢。但我真的不知道。

示例:

Input: 4

Output: [[4],[3,1],[1,3],[2,2],[1,1,2],[1,2,1],[2,1,1],[1,1,1,1]]

public class Perm{


    public List<List<Integer>> partition(int num, int maxNum, List<List<Integer>> arr, ArrayList<Integer> temp){
        if (num == 0) {
            arr.add((List<Integer>)temp.clone());
            temp.clear();
        }
        else{
            for (int i = Math.min(maxNum, num); i >= 1; i--) {
                temp.add(i);
                System.out.println(temp);
                partition(num-i, i, arr, temp);
            }
        }

        return arr;
    }

}

Answer 1

您已经非常接近了，但您需要在继续迭代之前撤消 temp.add(i)。使用 Deque 最容易完成此操作。而不是 List .

这就是我的写法:

public static List<List<Integer>> combosWithSum(int sum) {
    if (sum < 0)
        throw new IllegalArgumentException("Sum cannot be negative: " + sum);
    if (sum == 0)
        return Collections.emptyList();
    List<List<Integer>> result = new ArrayList<>();
    buildCombosWithSum(sum, new ArrayDeque<>(), result);
    return result;
}

private static void buildCombosWithSum(int sum, Deque<Integer> combo, List<List<Integer>> result) {
    for (int num = sum; num > 0; num--) {
        combo.addLast(num);
        if (num == sum)
            result.add(new ArrayList<>(combo));
        else
            buildCombosWithSum(sum - num, combo, result);
        combo.removeLast();
    }
}

测试

combosWithSum(5).forEach(System.out::println);

输出

[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 3]
[2, 2, 1]
[2, 1, 2]
[2, 1, 1, 1]
[1, 4]
[1, 3, 1]
[1, 2, 2]
[1, 2, 1, 1]
[1, 1, 3]
[1, 1, 2, 1]
[1, 1, 1, 2]
[1, 1, 1, 1, 1]

要按照问题中显示的顺序获取结果，请在 return result; 之前添加以下行:

result.sort(Comparator.comparingInt(List::size));

[5]
[4, 1]
[3, 2]
[2, 3]
[1, 4]
[3, 1, 1]
[2, 2, 1]
[2, 1, 2]
[1, 3, 1]
[1, 2, 2]
[1, 1, 3]
[2, 1, 1, 1]
[1, 2, 1, 1]
[1, 1, 2, 1]
[1, 1, 1, 2]
[1, 1, 1, 1, 1]