Java recursion problem

Question

I had a problem with the recursive interview question in Java, you need your help.

Write a **Java function** such that :: If an array from ints is given, is it possible to divide int into two groups, so that the sum of the two groups is the same: with these restrictions: all values ​​that are several of 5 must be in the same group , and all values ​​that are multiples of 3 (and not multiples of 5) must be in another. (No need for loops.)

split53({1,1}) → true
split53({1, 1, 1}) → false
split53({2, 4, 2}) → true

PS: It was an interview question for hewlett packard

Answer 1

The question easily comes down to the following: if you are given a set of integers numbers and an integer target , is it possible to find a subset of numbers with the sum equal to target ?
Let me know if the transition needs clarification.

This can be solved using DP in O(numbers.size * target) time. The idea is as follows

• When numbers.size is 0 , the only attainable amount is 0 .
• Suppose that numbers == {1, 3} , in this case there are sums {0, 1, 3, 4} . What if we add another element to numbers 4 ? Now all the old amounts can be reached and some new ones: {0 + 4, 1 + 4, 3 + 4, 4 + 4} . Thus, for numbers == {1, 3, 4} available sums are {0, 1, 3, 4, 5, 7, 8} .
• Thus, adding a number by number, you can build a list of reachable amounts.

Working example (it does not handle negative numbers, but you can easily fix this)

 boolean splittable(int[] numbers, int target) { boolean[] reached = new boolean[target + 1]; reached[0] = true; for (int number : numbers) { for (int sum = target - 1; sum >= 0; --sum) { if (reached[sum] && sum + number <= target) { reached[sum + number] = true; } } } return reached[target]; } 

Run it

 System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false 

change
I just noticed the "recursion" of the part of the requirement. Well, DP can be rewritten as recursion with memoization , if that is a strict requirement. This will save runtime.

change 2
By groups. You must assign elements divisible by 3 or 5 to the appropriate groups before proceeding with the algorithm. Let, say, the sum of all elements is s , the sum of elements divisible by 3 is s3 , and the sum of elements divisible by 5, but not 3, is s5 . In this case, after you have assigned these "special" elements, you need to divide the rest, so that the sum in one group is s/2 - s3 and in the other s/2 - s5 .

Answer 2

Very slow but working solution:

 static boolean canSplit(int[] arr, int lvl, int sum1, int sum2) { if (arr.length == lvl) { if (sum1 == sum2) { return true; } else { return false; } } if (arr[lvl] % 5 == 0) { return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2); } else if (arr[lvl] % 3 == 0) { return canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]); } return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2) || canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]); } 

Call function:

 canSplit(arr, 0, 0, 0); 

Answer 3

Here is a real recursive solution.

 private boolean split2(int index, int[] nums, int sum1, int sum2) { if (index >= nums.length) { return sum1 == sum2; } if (split2(index + 1, nums, sum1 + nums[index], sum2)) { return true; } if (split2(index + 1, nums, sum1, sum2 + nums[index])) { return true; } return false; } 

This code goes through the inclusion of each element in one of the groups. If in any combination the two groups are equal, it returns true. There are no loops used and in only one function.

Best for all

Answer 4

Code that is likely to make me fire. But it will work: D

Completely recursive, no less fatal.

 public boolean split53(int[] nums) { return split_fn(0, nums, 0, 0, false, false); } public boolean split_fn(int start, int[] nums, int left, int right, boolean fiveLeft, boolean chosen) { if (start >= nums.length) { if (left == right) return true; return false; } if (nums[start] % 5 == 0) { if (!chosen) { return split_fn(start + 1, nums, left + nums[start], right, true, true) || split_fn(start + 1, nums, left, right + nums[start], false, true); } else { return split_fn(start + 1, nums, left + ((fiveLeft) ? nums[start] : 0), right + ((!fiveLeft) ? nums[start] : 0), fiveLeft, chosen); } } if (nums[start] % 3 == 0 && nums[start] % 5 != 0) { if (!chosen) { return split_fn(start + 1, nums, left + nums[start], right, false, true) || split_fn(start + 1, nums, left, right + nums[start], true, true); } else { return split_fn(start + 1, nums, left + ((!fiveLeft) ? nums[start] : 0), right + ((fiveLeft) ? nums[start] : 0), fiveLeft, chosen); } } //standard case return split_fn(start + 1, nums, left + nums[start], right, fiveLeft, chosen) || split_fn(start + 1, nums, left, right + nums[start], fiveLeft, chosen); } 

Answer 5

I don't know how fast or slow the next solution is. But it is precisely this recursive backtracking solution that does not use loops as indicated in the question.

Here is the code snippet:

 public boolean split53(int[] nums) { int start = 0, firstPart = 0, secondPart = 0; if (split(start, nums, firstPart, secondPart)) { return true; } return false; } public boolean split(int start, int[] nums, int firstPart, int secondPart) { if (start >= nums.length) { return (firstPart == secondPart); } if ((start + 1) < nums.length && (nums[start] % 3 != 0) && (nums[start + 1] % 5 != 0) && split(start + 2, nums, firstPart + nums[start], secondPart + nums[start + 1])) { return true; } if ((start + 1) < nums.length && (nums[start + 1] % 3 != 0) && (nums[start] % 5 != 0) && split(start + 2, nums, firstPart + nums[start + 1], secondPart + nums[start])) { return true; } if ((nums[start] % 3 != 0) && split(start + 1, nums, firstPart + nums[start], secondPart)) { return true; } if ((nums[start] % 5 != 0) && split(start + 1, nums, firstPart, secondPart + nums[start])) { return true; } return false; } 

Hope this helps.