使用递归和回溯的 SubsetSum

Question

我已经编写了一个算法来 return 使用回溯和递归 (returns true/false)

例如：{5, 2, 3, 6} 目标 = 8 ==> 真 || {5, 2, 3, 6} 目标 = 20 ==> 假

我想修改我的算法，使其包含集合中可能存在的所有 5。我很难使用回溯和递归来解决这个问题。任何建议表示赞赏

例如：{5, 2, 3, 6} 目标 8 ==> 真 || {6, 2, 3, 5, 5} 目标 8 ==> False

我编写了一个算法，它递归地包含一个数字并检查总和，然后从总和中省略该数字，但我不知道如何修改我的算法以仅选择特定数字并将它们包含在总和中

public static void main(String argv[]) {
        int[] ints = { 10, 1, 3, 2 };
        int target = 5;
        int start = 0;
        System.out.println(groupSum(ints, target, 0, start));
    }

    public static boolean groupSum(int[] arr, int target, int sum, int start) {
        if (sum > target) {
            return false;
        }
        if (sum == target) {
            return true;
        }
        if (start >= arr.length) {
            return false;
        }
        //choose
        sum = sum + arr[start];
        //explore
        if (groupSum(arr, target, sum, start + 1))
            return true;
        //un-choose
        sum = sum - arr[start];
        return groupSum(arr, target, sum, start + 1);
    }

Answer 1

强制它只看包括 5 如果它看到它，并且只在最后检查 = sum 。像这样：

public static void main(String argv[]) {
    int[] ints = { 10, 1, 3, 2 };
    int target = 5;
    int start = 0;
    System.out.println(groupSum(ints, target, 0, start));
}

public static boolean groupSum(int[] arr, int target, int sum, int start) {
    if (sum > target) {
        return false;
    }
    // NOTE: sum == target inside of end of array check so all 5s are found.
    if (start >= arr.length) {
        return sum == target;
    }
    //choose
    sum = sum + arr[start];
    //explore
    if (groupSum(arr, target, sum, start + 1))
        return true;
    //un-choose
    // NOTE: can't unchoose 5
    if (5 == arr[start]) {
        return false;
    }
    sum = sum - arr[start];
    return groupSum(arr, target, sum, start + 1);
}

更新：这里是关于如何解决此类问题的建议。

非常清楚地说明您希望函数执行的操作。
非常清楚地说明您知道答案的基本案例是什么。
在复杂的情况下，找出如何将其简化为一个或多个更简单的问题。

只要您这样做了，您的递归代码就应该可以工作。如果您对如何修改有疑问，请从头开始，只复制之前您注意到可以保留的代码。

所以对于第一步，声明是，我们希望 groupSum 取一个正整数数组 arr，一个目标 target，一个部分和 sum 和 int start 以及 return 当您采用必须包含所有 5 的子集时，是否有可能使数组的其余部分总和为 target。

对于第二步，基本情况是：

我们已经超过target，接下来是false。
我们已经到达数组的末尾，在target，然后是true。
我们已经到了数组的末尾，正在吹target，然后是false。（我通过 return 比较将其与代码中的最后一个结合起来。）

第三步减量如下

如果我们能把当前的值加起来做成，答案就是true。
如果当前值不是5，我们不加，可以，答案是true。
否则为假

我试图以看起来最像您已有的方式编写代码。但是如果完全按照这个逻辑来写的话应该是这样的：

public static boolean groupSumWithAll5s(int[] arr, int target, int sum, int start) {
    // Base cases
    if (sum > target) {
        return false;
    }
    else if ((start >= arr.length) && (sum == target)) {
        return true;
    }
    else if (start >= arr.length) {
        return false;
    }

    // Recursive cases.
    if (groupSumWithAll5s(arr, target, sum + arr[start], start + 1)) {
        return true;
    }
    else if ((arr[start] != 5) && groupSumWithAll5s(arr, target, sum, start + 1)) {
        return true;
    }
    else {
        return false;
    }
}

使用递归和回溯的 SubsetSum

SubsetSum using recursion and backtracking

algorithm

recursion

backtracking

subset-sum