[問題] Java 遞迴 recursion/backtracking groupSum
最近在練習解題, 但對於這題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://www.ptt.cc/bbs/java/M.1550842356.A.AEA.html
→
02/22 21:46,
5年前
, 1F
02/22 21:46, 1F
→
02/22 21:48,
5年前
, 2F
02/22 21:48, 2F
→
02/22 21:49,
5年前
, 3F
02/22 21:49, 3F
→
02/22 21:49,
5年前
, 4F
02/22 21:49, 4F
→
02/22 21:50,
5年前
, 5F
02/22 21:50, 5F
→
02/22 21:50,
5年前
, 6F
02/22 21:50, 6F
→
02/22 21:52,
5年前
, 7F
02/22 21:52, 7F
→
02/23 02:28,
5年前
, 8F
02/23 02:28, 8F
→
02/23 02:34,
5年前
, 9F
02/23 02:34, 9F
→
02/23 02:34,
5年前
, 10F
02/23 02:34, 10F
推
02/23 11:58,
5年前
, 11F
02/23 11:58, 11F
→
02/23 11:58,
5年前
, 12F
02/23 11:58, 12F
推
02/23 12:03,
5年前
, 13F
02/23 12:03, 13F
→
02/23 12:03,
5年前
, 14F
02/23 12:03, 14F
推
02/26 09:32,
5年前
, 15F
02/26 09:32, 15F
→
02/27 22:26,
5年前
, 16F
02/27 22:26, 16F
→
02/27 22:27,
5年前
, 17F
02/27 22:27, 17F
※ 編輯: yogaxiao (123.193.222.33), 02/27/2019 22:29:57
java 近期熱門文章
PTT數位生活區 即時熱門文章
