4

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

0lune
  • 69
  • 3

1 Answers1

4

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]
vszholobov
  • 2,133
  • 1
  • 8
  • 23
  • Have a look at this one: [Find all combination that sum to N with multiple lists](https://stackoverflow.com/questions/34970848/find-all-combination-that-sum-to-n-with-multiple-lists/34971783#34971783) – tibibou Aug 13 '22 at 20:46