Generating all permutation of numbers that sums up to N

Question

I am writing a program to create a recursive permutation of all numbers<=N that add up to a given number N. However I am at a loss on how to create that permutation. Any insights would be appreciated.

At first I was trying to partition the numbers using the partition function and permutate each number set later, however I don't think it would work and the best way is the recursively permutate while summing the numbers which is way over my head.

Sorry if this sounds really dumb. But I really have no idea.

Example:

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

You were very close, but you need to undo temp.add(i) before continuing the iteration. That is most easily done using a Deque instead of a List.

This is how I would write it:

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

Test

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

Output

[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]

To get the result in the order shown in the question, add the following line before 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]