子集和的Java递归解法

Question

我被告知要编写一个递归函数，它包含一个起始索引、一个整数数组和一个目标和，你的目标是找出整数数组的子集是否与目标和相加

我给出的例子是groupSum（0，{2,4,8}，10）应该返回true，因为2和8加起来就是目标10。到目前为止，我所能做的只是基本情况

public boolean groupSum(int start, int[] nums, int target) {
    if (nums.length == 0)
    {
        return false;
    }
    else if (start == nums.length - 1)
    {
        return nums[start] == target;
    }
    else
    {
        ?????
    }
}

我不知道实际的递归调用应该去哪里。因为我不能在调用之间传递一个集合和，所以我不知道如何在每次递归调用中添加一个数字，直到达到目标。此外，正如示例中所示，我不知道如何让代码意识到一个数字不起作用，然后跳过它，就像示例中的4一样。我的思路是，我应该从int target中一次减去一个数字，然后用一个新的起点和target的新值递归调用该方法，但我不知道如何使用它来查看是否存在有效的子集

我将非常感谢任何能帮助我理解如何解决这个问题的帮助，这样我就能完成它。谢谢

Answer 1

这应该根据给定的条件工作。 最初是start = 0

boolean subsetSum(int start, int[] nums, int target) {
     // target is the sum you want to find in the nums array
     if (target == 0) return true;
     if (start > nums.length-1 || nums.length == 0)
        return false;
     if (nums[start] > target) 
        return subsetSum(start+1, nums, target);
     return subsetSum(start+1, nums, target) || subsetSum(start+1, nums, target - nums[start]);
}

Answer 2

dynamic programming。也许这对你有帮助

Answer 3

这是一个有效的版本。有关解释，请参见代码中的注释

public static boolean recursiveSumCheck(int target, int[] set) {
    //base case 1: if the set is only one element, check if element = target
    if (set.length == 1) {
        return (set[0] == target);
    }

    //base case 2: if the last item equals the target return true
    int lastItem = set[set.length - 1];
    if (lastItem == target) {
        return true;
    }

    //make a new set by removing the last item
    int[] newSet = new int[set.length - 1];
    for (int newSetIndex = 0; newSetIndex < newSet.length; newSetIndex++) {
        newSet[newSetIndex] = set[newSetIndex];
    }

    //recursive case: return true if the subset adds up to the target
    //                OR if the subset adds up to (target - removed number)
    return (recursiveSumCheck(target, newSet) || recursiveSumCheck(target - lastItem, newSet));
}

Answer 4

正如你所指出的，你可以改变目标，而不是通过一个集体的总和。一旦目标为零，您就知道您已经找到了解决方案（通过不选择剩余项的任何成员）

因此，在psueduo代码中：

hasMembersThatSumTo(list, total):
    if total == 0
        return true
    else if total < 0 or list is empty
        return false
    else
        int first = list.pop
        return hasMembersThatSumTo(list, total - first)
            or hasMembersThatSumTo(list, total)

“or”语句中的两种情况是寻找当前元素在和中或不在和中的情况