Java - 子集总和的递归解决方案

我被告知编写一个递归函数，该函数采用开始索引，整数数组和目标总和，您的目标是查找整数数组的子集合是否合计目标总和。Java - 子集总和的递归解决方案

我给出的例子是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，但我不知道如何使用它来查看是否有有效的子集。

我将不胜感激任何帮助，可以帮助我了解如何解决此问题，以便我可以完成它。谢谢！

来源

2016-10-04 user3204121

提示：检查一组3,2和1是否可以合计为8.从3开始。您有两种情况。你需要检查剩余的集合（2和1）是否可以自己加起来为8。您还需要检查剩余集合是否可以与包含3的IE加起来为8，IE是否剩余集合可以加起来为（8 - 3）。 – nhouser9

正如你指出的，你可以改变目标，而不是传递一个总和。一旦目标为零，你就知道你已经有了一个解决方案（通过选择没有其余项目的成员）。

所以，在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)

这两起案件中“或”声明正在寻找这种情况在目前的元素是或不是的总和。

来源

2016-10-04 02:47:08 sprinter

这是一个工作版本。请参阅代码中的注释以获得解释。

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

来源

2016-10-04 03:00:52 nhouser9

dynamic programming。也许这会帮助你。

来源

2016-10-04 03:07:52

Java - 子集总和的递归解决方案

回答

相关问题