时间戳

首页 > 解决方案 > 使用递归和回溯的 SubsetSum

algorithm - 使用递归和回溯的 SubsetSum

问题描述

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

例如：{5, 2, 3, 6} 与 Target = 8 ==> True || {5, 2, 3, 6} 目标 = 20 ==> False

我想修改我的算法，使其包含集合中可能存在的所有 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);
    }

标签： algorithmrecursionbacktrackingsubset-sum

解决方案

强制它只看包括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. 非常清楚地说明您希望该功能做什么。
  2. 非常清楚地说明您知道答案的基本案例或案例。
  3. 在复杂的情况下，弄清楚如何将其简化为一个或多个更简单的问题。

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

因此，对于第一步，语句是，我们希望 groupSum 采用一个arr正整数数组、一个 target target、一个部分总和sum和一个 intstart并返回是否有可能让数组的其余部分target相加必须包含所有 5 的子集。

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

  • 我们已经超过了target，那就是false。
  • 我们已经到达数组的末尾并且在target，那么它就是true。
  • 我们已经到了数组的尽头并且是一击target，然后是false。（我通过返回一个比较将它与代码中的最后一个结合起来。）

第三步，减量如下。

  • 如果我们可以添加当前值并制作它，答案是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;
    }
}

推荐阅读