Пошук, якщо існує підмножина, що його сума дорівнює цілі, після чого друкує його - java, backtracking

Я намагаюся знайти, чи існує підмножина, яка сумою дорівнює меті, а потім друкує її. Я новачок у Java, і рекурсія часом дещо бентежить

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

Відповіді:

Загалом рекурсія стає менш заплутаною, якщо ви запитаєте себе:

1. Це дуже проста ситуація, яка має очевидну відповідь; і
2. Як я можу перетворити непросту ситуацію на просту?

У вашому випадку відповідь:

1. якщо підмножина порожня, то умові задовольняє лише цільова сума 0
2. якщо підмножина не порожня, перевірте, чи є у набору без першого елемента підмножина, яка дорівнює сумі, або сума мінус перший елемент

Переклад цих відповідей у ​​код:

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

Або, використовуючи масиви:

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

Якщо ви просто хочете надрукувати всі підмножини:

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

У всіх випадках візерунок абсолютно однаковий.