生成总数为N的所有数字置换

Question

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

起初，我试图使用分区函数对数字进行划分，然后对每个数字集进行置换，但是我认为这不起作用，最好的方法是在对数字求和时进行递归置换，这超出了我的头。

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

示例：

输入：4

输出：[[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而不是Deque最容易做到这一点。

这是我的写法：

List

Test

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;