使用递归和回溯的SubsetSum

Question

我编写了一个算法，用于返回一组数字的子集是否将使用回溯和递归（返回真/假）与给定目标求和

例如：{5,2,3,6}，目标为8==

我想修改我的算法，以便它包括集合中可能存在的所有5。我很难用回溯和递归来解决这个问题。任何建议都不胜感激

例如：{5,2,3,6}目标8==

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

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

更新：以下是关于如何解决类似问题的建议。

1. 非常清楚地说明您希望函数执行的操作

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

因此，对于第一步，语句是，我们希望groupSum获取一个正整数数组，一个targettarget，一个部分和sum和一个intstart，并返回在获取必须包含所有5的子集时，是否可以将数组的其余部分和到target。

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

• 我们已经超过了目标，那么它是错误

对于第三步，减少如下。

• 如果我们可以添加当前值并使其生效，则答案为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;
    }
}