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

我正在编写一个程序来创建所有小于等于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 RPal {
    private Map<Integer, List<List<Integer>>> storageAllRPals;

    public RPal() {
        storageAllRPals = new HashMap<>();
        storageAllRPals.put(0, Arrays.asList(Arrays.asList()));
        storageAllRPals.put(1, Arrays.asList(Arrays.asList(1)));
    }

    private List<List<Integer>> computeAllRPals(int n) {
        partition(n);
        return null;
    }

    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;
    }

    public List<List<Integer>> allRPals(int n) {

        List<List<Integer>> answer = storageAllRPals.get(n);
        if (answer == null) {
            answer = computeAllRPals(n);
            storageAllRPals.put(n, answer);
        }

        return answer;
    }

    public static void main(String[] args) {
        RPal rPal = new RPal();

        // System.out.println(rpal.allRpals(4));
        // System.out.println(rPal.allRPals(6));

    }
}
评论