java - Building permutation that sums to a number efficiently

Question

I am looking to generate more permutation that sums up to a given number N, however this time more efficiently. Since by general methods, it takes forever to create 100+ permutations.

However I'm at another impasses where I find it extremely difficult to build upward permutations that utilized the permutations that are already solved n-1 to generate every permutation that sums to n.

I would greatly appreciate any help! I still a total newbie, so sorry if it seems like an easy question. but this is bending my mind!

Input(n): 4

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

import java.util.*;
import javax.naming.PartialResultException;

public class Perm {
    private List<List<Integer>> computePerm(int n) {
        // I totally lost it here
        if (n == 0) {
            return computePerm(0);
        } else {
            List<Integer> arr2 = new ArrayList<>();
            for (List<Integer> entry : arr1) {
                for (int i = 0; i < entry.size(); i++) {
                    arr2.add(entry.get(i)); // This obviously doesn't work
                }
            }
        }
        return computePerm(n);
    }

    public static void main(String[] args) {
        Perm perm1 = new Perm();
        System.out.println(computePerm(4));
    }
}

Answer 1

This can be done recursively. The stack contains what you've previously built and adds onto it.

While I'd worry about correctness first, then optimization, I don't see a way to get around the fact that you'll need to enumerate each of the integer partitions, so the complexity is going to be exponential unless I'm missing something.

import java.util.ArrayDeque;
import java.util.ArrayList;

class Main {
    public static ArrayList<ArrayList<Integer>> partition(int n) {
        var result = new ArrayList<ArrayList<Integer>>();
        partition(n, new ArrayDeque<>(), result);
        return result;
    }

    private static void partition(int n, ArrayDeque<Integer> path, 
                                  ArrayList<ArrayList<Integer>> result) {
        if (n == 0) result.add(new ArrayList<Integer>(path));

        for (int i = 1; i <= n; i++) {
            path.offer(i);
            partition(n - i, path, result);
            path.pop();
        }
    }

    public static void main(String[] args) {
        for (var result : partition(4)) {
            for (int i : result) {
                System.out.print(i + " ");
            }

            System.out.println();
        }
    }
}

Output:

1 1 1 1 
1 1 2 
2 2 1 
1 3 
2 1 1 
1 2 
3 1 
4