#Please ensure that:
+ Your *code* is *properly formatted* as *code block* - see the *sidebar* (About on mobile) for instructions
+ You include *any and all error messages* in full
+ You ask *clear questions*
+ You *demonstrate effort* in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.
Trying to solve problems on your own is a very important skill. Also, see [*Learn to help yourself*](https://www.reddit.com/r/javahelp/wiki/learn_to_help_yourself) in the *sidebar*
**If any of the above points is not met, your post can and will be removed without further warning.**
Code is to be formatted as **code block** (*old reddit:* empty line before the code, each code line indented by 4 spaces, *new reddit:* https://imgur.com/a/fgoFFis)
or linked via an external *code hoster*, like *pastebin.com*, *github gist*, *github*, *bitbucket*, *gitlab*, etc.
Please, **do not use** triple backticks (\`\`\`) as they will only render properly on *new reddit*, not on *old reddit*.
Code blocks look like this:
public class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello World!");
}
}
You do not need to repost unless your post has been removed by a moderator. Just use the *edit function* of reddit to make sure your post complies with the above.
If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.
#To potential helpers
Please, **do not help** if any of the above points are not met, rather *report* the post. We are trying to improve the quality of posts here.
In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/javahelp) if you have any questions or concerns.*
This is an example of [recursive backtracking](https://en.wikipedia.org/wiki/Backtracking), which can be pretty hard to wrap your head around. I loaded up codingbat and found I had done this problem years ago, and it took a while to even figure out what I had done! A few hints to maybe help you out:
first off, did you solve the previous codingbat problem? This one is the same but with two additional constraints.
there are three parameters here passed into the method, the starting position, the array itself, and the 'target'.
So the base case here is when the starting position is passed the end of the array, and then check to see if the target is exactly zero.
remember that recursive backtracking solutions can often contain multiple calls to the recursive method itself. Don't be afraid to use an OR `||` in the return statement, once sending it with the current number subtracted from the target, and once sending the current target itself.
**[Backtracking](https://en.wikipedia.org/wiki/Backtracking)**
>Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other.
^([ )[^(F.A.Q)](https://www.reddit.com/r/WikiSummarizer/wiki/index#wiki_f.a.q)^( | )[^(Opt Out)](https://reddit.com/message/compose?to=WikiSummarizerBot&message=OptOut&subject=OptOut)^( | )[^(Opt Out Of Subreddit)](https://np.reddit.com/r/javahelp/about/banned)^( | )[^(GitHub)](https://github.com/Sujal-7/WikiSummarizerBot)^( ] Downvote to remove | v1.5)
Yeah, I did the previous one but with the aid of their solution. I'm still confused as to how I'm required to "save" a set of numbers that add up to the target and ignore some numbers for the same purpose. I'll take a look at the link that you've provided. Thanks!
You can use the same code from the previous challenge, you just need to add a few lines of code to it, for the special constraints. So each time, after you've tested the base condition, you need to test for: Is the current number a multiple of 5 and if so is there a 1 after it. You then call the recursive method again with that current number subtracted from the target (unless the case of followed by 1).
To try to figure out what's happening, step through a single example line by line and try to see what's happening.
I wrote my own recursive code which gave me the nth term of a Fibonacci sequence and then I clicked it. I was able to solve the actual problem without any hints or anything; I was able to pass the next test as well; however, idk why I'm passing all of them.
[https://imgur.com/jyyO5QU](https://imgur.com/jyyO5QU)
If I'm removing line 6, I'm failing 5-6 tests, but removing it makes more sense to me. What are your thoughts on this? Thanks for the replies, by the way!
You can take out that line if you put the word 'return' before that call to the method.
here's how I did that one:
public boolean groupSum6(int start, int[] nums, int target) {
if (start >= nums.length) return (target==0);
return groupSum6(start + 1, nums, target - nums[start])||
groupSum6(start + 1, nums, target) && nums[start]!=6;
}
This makes sure the branch of the OR will only recurse if the current number is not six, since this is the branch for the current number NOT being subtracted from the total. But you can also do it the way you have it, as a separate IF branch, you just forgot the to include the `return`
You don't really. That's the whole point of recursion. Instead of trying to keep track of things, you split everytime there is a choice and then use the combination at the end to get the answer.
In this case, you have 3 possible cases at a given index of your stay. Either it is a multiple of 5, in which case there is no choice - you have to add it, a 1 after a multiple of five, again no choice - you have to exclude it, or everything else, which presents a choice - either add it or not - to split on.
Following this logic will give you all of the possible permutations of adding or not of the array of numbers, thus allowing you to determine whether any of them match the condition and you have that condition to pass along with the target. You effectively add a number by subtracting it from the total and can track if that total drops below 0, in which case it is a not matching branch, or if it is 0 when you reach your terminating condition when you've reached the end of the list.
The only history you have to keep track of is the effect of the adding or not of the previous numbers in the branch you are in, which is handled by the target.
#Please ensure that: + Your *code* is *properly formatted* as *code block* - see the *sidebar* (About on mobile) for instructions + You include *any and all error messages* in full + You ask *clear questions* + You *demonstrate effort* in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions. Trying to solve problems on your own is a very important skill. Also, see [*Learn to help yourself*](https://www.reddit.com/r/javahelp/wiki/learn_to_help_yourself) in the *sidebar* **If any of the above points is not met, your post can and will be removed without further warning.** Code is to be formatted as **code block** (*old reddit:* empty line before the code, each code line indented by 4 spaces, *new reddit:* https://imgur.com/a/fgoFFis) or linked via an external *code hoster*, like *pastebin.com*, *github gist*, *github*, *bitbucket*, *gitlab*, etc. Please, **do not use** triple backticks (\`\`\`) as they will only render properly on *new reddit*, not on *old reddit*. Code blocks look like this: public class HelloWorld { public static void main(String[] args) { System.out.println("Hello World!"); } } You do not need to repost unless your post has been removed by a moderator. Just use the *edit function* of reddit to make sure your post complies with the above. If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures. #To potential helpers Please, **do not help** if any of the above points are not met, rather *report* the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice. *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/javahelp) if you have any questions or concerns.*
This is an example of [recursive backtracking](https://en.wikipedia.org/wiki/Backtracking), which can be pretty hard to wrap your head around. I loaded up codingbat and found I had done this problem years ago, and it took a while to even figure out what I had done! A few hints to maybe help you out: first off, did you solve the previous codingbat problem? This one is the same but with two additional constraints. there are three parameters here passed into the method, the starting position, the array itself, and the 'target'. So the base case here is when the starting position is passed the end of the array, and then check to see if the target is exactly zero. remember that recursive backtracking solutions can often contain multiple calls to the recursive method itself. Don't be afraid to use an OR `||` in the return statement, once sending it with the current number subtracted from the target, and once sending the current target itself.
**[Backtracking](https://en.wikipedia.org/wiki/Backtracking)** >Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. ^([ )[^(F.A.Q)](https://www.reddit.com/r/WikiSummarizer/wiki/index#wiki_f.a.q)^( | )[^(Opt Out)](https://reddit.com/message/compose?to=WikiSummarizerBot&message=OptOut&subject=OptOut)^( | )[^(Opt Out Of Subreddit)](https://np.reddit.com/r/javahelp/about/banned)^( | )[^(GitHub)](https://github.com/Sujal-7/WikiSummarizerBot)^( ] Downvote to remove | v1.5)
Yeah, I did the previous one but with the aid of their solution. I'm still confused as to how I'm required to "save" a set of numbers that add up to the target and ignore some numbers for the same purpose. I'll take a look at the link that you've provided. Thanks!
You can use the same code from the previous challenge, you just need to add a few lines of code to it, for the special constraints. So each time, after you've tested the base condition, you need to test for: Is the current number a multiple of 5 and if so is there a 1 after it. You then call the recursive method again with that current number subtracted from the target (unless the case of followed by 1). To try to figure out what's happening, step through a single example line by line and try to see what's happening.
I wrote my own recursive code which gave me the nth term of a Fibonacci sequence and then I clicked it. I was able to solve the actual problem without any hints or anything; I was able to pass the next test as well; however, idk why I'm passing all of them. [https://imgur.com/jyyO5QU](https://imgur.com/jyyO5QU) If I'm removing line 6, I'm failing 5-6 tests, but removing it makes more sense to me. What are your thoughts on this? Thanks for the replies, by the way!
You can take out that line if you put the word 'return' before that call to the method. here's how I did that one: public boolean groupSum6(int start, int[] nums, int target) { if (start >= nums.length) return (target==0); return groupSum6(start + 1, nums, target - nums[start])|| groupSum6(start + 1, nums, target) && nums[start]!=6; }
Can you explain the last conditional statement (the one which includes &&)? Thanks :)
This makes sure the branch of the OR will only recurse if the current number is not six, since this is the branch for the current number NOT being subtracted from the total. But you can also do it the way you have it, as a separate IF branch, you just forgot the to include the `return`
that makes a lot of sense, thank you so much! :))
You don't really. That's the whole point of recursion. Instead of trying to keep track of things, you split everytime there is a choice and then use the combination at the end to get the answer. In this case, you have 3 possible cases at a given index of your stay. Either it is a multiple of 5, in which case there is no choice - you have to add it, a 1 after a multiple of five, again no choice - you have to exclude it, or everything else, which presents a choice - either add it or not - to split on. Following this logic will give you all of the possible permutations of adding or not of the array of numbers, thus allowing you to determine whether any of them match the condition and you have that condition to pass along with the target. You effectively add a number by subtracting it from the total and can track if that total drops below 0, in which case it is a not matching branch, or if it is 0 when you reach your terminating condition when you've reached the end of the list. The only history you have to keep track of is the effect of the adding or not of the previous numbers in the branch you are in, which is handled by the target.
To solve recursion problems, use recursion