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 - 子集總和的遞歸解決方案

回答

相關問題