作者yogaxiao (電腦壞了ˊ_ˋ)
看板java
標題[問題] Java 遞迴 recursion/backtracking groupSum
時間Fri Feb 22 21:32:33 2019
最近在練習解題, 但對於這題recursion的答案一直不是很理解,
有把解答貼到eclipse用debugger刷了好幾遍但還是不懂它跳的順序...
不知道是否有文字敘述能幫助我理解, 感謝各位
Problem:
Given an array of ints, is it possible to choose a group of some of the ints,
such that the group sums to the given target? This is a classic backtracking
recursion problem. Once you understand the recursive backtracking strategy in
this problem, you can use the same pattern for many problems to search a
space of choices. Rather than looking at the whole array, our convention is
to consider the part of the array starting at index start and continuing to
the end of the array. The caller can specify the whole array simply by
passing start as 0. No loops are needed -- the recursive calls progress down
the array.
groupSum(0, {2, 4, 8}, 10) → true
groupSum(0, {2, 4, 8}, 14) → true
groupSum(0, {2, 4, 8}, 9) → false
Solution:
public boolean groupSum(int start, int[] nums, int target) {
if (start >= nums.length) {
return (target == 0);
}
if (groupSum(start + 1, nums, target - nums[start])) return true;
if (groupSum(start + 1, nums, target)) return true;
return false;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.222.33
※ 文章網址: https://webptt.com/m.aspx?n=bbs/java/M.1550842356.A.AEA.html
1F：→ ssccg: 這重點在演算法不在程式怎麼跳吧 02/22 21:46
2F：→ ssccg: 這算很單純的題目，求 nums[0 ~ n] 有沒有辦法加出target 02/22 21:48
3F：→ ssccg: 以nums[0]來看只有兩種可能，target裡面有加進nums[0] → 02/22 21:49
4F：→ ssccg: 求 nums[1 ~ n] 有沒有辦法加出 target - nums[0] 02/22 21:49
5F：→ ssccg: target裡面沒有加nums[0] → 02/22 21:50
6F：→ ssccg: 求 nums[1 ~ n] 有沒有辦法加出 target 02/22 21:50
7F：→ ssccg: 一開始start = 0，每次遞迴就start = start + 1 02/22 21:52
8F：→ yogaxiao: 因為是自學程式，目前還沒有學過演算法orz 02/23 02:28
9F：→ yogaxiao: 有理解你的意思，但不懂為何code是這樣寫，覺得有點抽象 02/23 02:34
10F：→ yogaxiao: 搭不起來... 02/23 02:34
11F：推 haha02: 可以看一下backtracking的介紹 一般會有 pseudo code幫助 02/23 11:58
12F：→ haha02: 理解 02/23 11:58
13F：推 haha02: 這題的話 邏輯就是每個元素看一次 取或不取該元素都嘗試 02/23 12:03
14F：→ haha02: 看是否有一個情況可以滿足條件(剛好把target扣到0) 02/23 12:03
15F：推 kurakidream: Backtracking 畫recursive tree 出來看比較好懂 02/26 09:32
16F：→ yogaxiao: 謝謝,後來有往recursive tree方向去找資料,畫出來之後有 02/27 22:26
17F：→ yogaxiao: 清楚多了,原本是連怎麼畫tree都不知道.. 02/27 22:27
※ 編輯: yogaxiao (123.193.222.33), 02/27/2019 22:29:57