Boolean Recursion with multiples of 5 included

user_14087174 0
Viewed 161

This is the problem I'm working on: "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 with these additional constraints: all multiples of 5 in the array must be included in the group. If the value immediately following a multiple of 5 is 1, it must not be chosen. (No loops needed.)"

I tried the following:

public boolean groupSum5(int start, int[] nums, int target) {
  if (start == nums.length) return (target == 0);
  if (groupSum5(start + 1, nums, target - nums[start]) && nums[start] % 5 == 0)
    return true;
  if (groupSum5(start + 1, nums, target)) return true;
  return false;
}

But it only gets the multiples of 5, and I tried this:

public boolean groupSum5(int start, int[] nums, int target) {
  if (start == nums.length) return (target == 0);
  if (groupSum5(start + 1, nums, target - nums[start]) && nums[start] % 5 == 0)
    return true;
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  if (groupSum5(start + 1, nums, target)) return true;
  return false;
}

but it does not work, since sometimes the multiples of 5 are not included.

I know my code does not fullfil the second constraint, yet.

Any ideas?

Edit: enter image description here

recursion boolean java
1 Answers

if (groupSum5(start + 1, nums, target - nums[start]))

For each number in your input, you need to choose whether to include it, or not include it. This if is the 'include it' option: That's why you reduce the target by the value.

&& nums[start] % 5 == 0

... so this means: It is impossible to include any given value, unless it is a multiple of 5. Which is not what the problem description wants you to do!

What the problem description wants you to do is: If the number you're on is a multiple of 5, then it MUST be included. You cannot opt not to include it.

Thus, you are sticking the constraint on the wrong if, and the wrong way around. What you actually want is for the second if, which covers the 'lets not pick this number' to be modified:

if (!num[start] % 5 == 0 && groupSum5(start, nums, target)) return true;

In other words: If the number we are on is NOT a multiple of 5, then try not including this number and see if that works out. (Because trying to not include it when it IS a multiple of 5, is invalid).

If the value immediately following a multiple of 5 is 1, it must not be chosen.

That is another constraint, and this one must be applied to the first if (the one that represents 'lets include this number'). That if needs some additional && to filter -OUT- the case where the number you are on is a 1, AND it is not the first number in the sequence, AND the previous number in the sequence is a multiple of 5: In that case, 'include the number' is not a valid move.

Use inverted conditions (with a ! in front) and &&, analogous to the above example. What you want to accomplish is that the step of 'try including this number and then see if we can work it out by applying this algorithm to the remainder of the list' is simply skipped if that step isn't valid due to the additional constraints.

user_7686440
Related