作者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/cn.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