Find all possible combinations of numbers to reach a given sum without a given set of numbers (Java) [closed]

Question

How would you find all the integer(excluding negative) combinations of a given number without a given set of numbers? I would imagine it most similar to finding solutions to a stars and bars problem.

For example,

• Find all combinations of 3 numbers that sum to 3
• Result: (0,0,3) (0,1,2) (0,2,1) (0,3,0) (1,0,2) (1,1,1) (1,2,0) (2,0,1) (2,1,0) (3,0,0)

I found something similar implemented in Python. Is it possible to do this in Java? General bars and stars

Answer 1

You can find all possible combinations of n positive numbers with the sum of target using Stack and recursion

public class Test {
    private static final int n = 3;
    private static final int target = 3;

    public static void main(String[] args) {
        Stack<Integer> terms = new Stack<>();

        sums(terms, 0);
    }

    public static void sums(Stack<Integer> terms, int curSum) {
        if(terms.size() == n - 1) {
            terms.add(target - curSum);
            System.out.println(terms);
            terms.pop();
            return;
        }

        for(int i = 0; i <= target - curSum; i++) {
            terms.add(i);
            sums(terms, curSum + i);
            terms.pop();
        }
    }
}

Output

[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]