搜索是否存在其和等于目标的子集然后打印它

Question

我正在尝试查找是否存在其总和等于目标的子集，然后将其打印出来。我是 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);
}

Answer 1

如果您问自己：

一般来说，递归会变得不那么混乱：

有一个很明显的答案的非常简单的情况是什么？和
如何将不简单的情况变成简单的情况

对于你的情况，答案是：

如果子集为空，则只有目标和为0满足条件
如果子集不为空，检查没有第一项的集合是否有等于总和或总和减去第一项的子集

将这些答案翻译成代码：

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

在所有情况下，模式都完全相同。

搜索是否存在其和等于目标的子集然后打印它

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

java

backtracking