給定一個可能包含重復項的 int 陣列。我需要找出陣列是否可以產生sum帶有k元素的？
我現在正在嘗試使用遞回，但目前我沒有得到任何結果。我在正確設定基本情況時遇到了問題。
static boolean groupSum(int[] nums, int k, int sum) {
if (sum == 0)
return true;
if (k > nums.length || sum != 0)
return false;
if (groupSum(nums, k, sum - nums[k - k] - nums[k - k 1] - nums[k - k 2]))
return true;
if (groupSum(nums, k, sum - nums[k - k 1] - nums[k - k 2] - nums[k - k 3]))
return true;
else
return false;
}
uj5u.com熱心網友回復：
您的遞回方法的基本情況sum == 0不正確：不是充分條件，您還必須檢查k == 0. 如果sum是，0但您仍然必須使用更多元素，那么結果true是不正確的。
該方法的遞回部分也有一些錯誤。總和的元素數量k不會減少。
此外，您必須跟蹤陣列中的位置。我的意思是你需要遍歷陣列。在對每個元素進行迭代時，只有兩個選項：應用它（k從總和中減去并減去當前值）或丟棄它。在這兩種情況下，您都必須增加作為引數傳遞的位置。
這就是它可以修復的方式：
public static boolean groupSum(int[] nums, int k, int pos, int sum) {
if (sum == 0 && k == 0) {
return true;
}
if (sum < 0) {
return false;
}
boolean result = false;
for (int i = pos; i < nums.length; i ) {
boolean takeElement = groupSum(nums, k - 1, pos 1, sum - nums[i]);
boolean discardElement = groupSum(nums, k, pos 1, sum);
result = takeElement || discardElement;
if (result) { // a combination that yield the target sum was found
break;
}
}
return result;
}
還有另一種選擇如何實作此方法。但請注意：它會變慢并顯著增加記憶體消耗。
這種方法需要在每次遞回方法呼叫時創建一個長度減 1的給定陣列的副本，并將其作為引數傳遞。在此版本中，呼叫方法時始終使用位置元素，因此不需要跟蹤陣列中的位置。主要邏輯保持不變：一個新元素既可以用于貢獻，也可以被丟棄。0sum
public static boolean groupSum(int[] nums, int k, int sum) {
if (sum == 0 && k == 0) {
return true;
}
if (sum < 0 || nums.length == 0) {
return false;
}
boolean takeElement = groupSum(Arrays.copyOfRange(nums, 1, nums.length), k - 1, sum - nums[0]);
boolean discardElement = groupSum(Arrays.copyOfRange(nums, 1, nums.length), k, sum);
return takeElement || discardElement;
}
public static void main(String[] args) {
// sum of 1, 2, 3, 4, 5 yields 15 - expected true
System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 5, 0, 15));
// it's impossible with only one element - expected false
System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 1, 0, 10));
// sum of 4, 5, 6 yields 15 - expected true
System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3, 0, 15));
}
輸出
true
false
true
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/430692.html
下一篇：在javascript中使用filter()來實作curriable()是可行的，但是，uisngmap()是可行的，為什么？