Search if there exist a subset that its sum equals the goal then prints it

Question

I am trying to find if there exist a subset that its sum equals the goal then prints it. I am new in java and recursion is a bit confusing sometimes

void sumOfSubsets(int n, int[] w, int W) {
    if (W == 0)
        return;

    if ((W < 0) || (n < 0))
        return;

    if (W == 0) {
        System.out.print(w[n] + " ");
        return;
    }

    sumOfSubsets(n - 1, w, W);
}

Answer 1

In general recursion becomes less confusing if you ask yourself:

1. What's a very simple situation that has an obvious answer; and
2. How can I make a non-simple situation into a simple one

In your case the answer are:

1. if the subset is empty, then only a target sum of 0 satisfies the condition
2. if the subset isn't empty, check if the set without the first item has a subset that equals the sum, or the sum minus the first item

Translating those answers to code:

boolean hasSumEqualTo(List<Integer> list, int sum) {
    if (list.isEmpty())
        return sum == 0;
    int first = list.remove(0);
    return hasSumEqualTo(list, sum) || hasSumEqualTo(list, sum - first);
}

Or, using arrays:

boolean hasSumEqualTo(int i, int[] list, int sum) {
    if (i == list.length)
        return sum == 0;
    return hasSumEqualTo(i + 1, list, sum) || hasSumEqualTo(i + 1, list, sum - list[i]);
}

If you just want to print all subsets:

void printSubsetsThatSumTo(String current, List<Integer> list, int sum) {
    if (list.isEmpty()) {
        if (sum == 0)
            System.out.println(current);
    } else {
        int first = list.remove(0);
        printSubsetsThatSumTo(current, list, sum);
        printSubsetsThatSumTo(current + " " + first, list, sum - first);
    }
}

In all cases the pattern is exactly the same.