Java Recursion Problem

I had a recursion interview question problem in Java,Need your help on this.

Write a **Java function** such that :: Given an array of ints, is it possible to divide the ints into two groups, so that the sum of the two groups is the same, with these constraints: all the values that are multiple of 5 must be in one group, and all the values that are a 开发者_Go百科multiple of 3 (and not a multiple of 5) must be in the other. (No loops needed.)

split53({1,1}) → true

split53({1, 1, 1}) → false

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

PS:This was a Interview Question for hewlett packard

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

It can be solved with DP in O(numbers.size * target) time. The idea is following

1. When numbers.size is 0, the only reachable sum is 0.
2. Suppose we have numbers == {1, 3}, in this case sums {0, 1, 3, 4} are available. What if we add another element to numbers, 4? Now, all old sums can still be reached and some new ones too: {0 + 4, 1 + 4, 3 + 4, 4 + 4}. Thus, for numbers == {1, 3, 4}, available sums are {0, 1, 3, 4, 5, 7, 8}.
3. In this fashion, adding number by number, you can build the list of reachable sums.

A working example (it doesn't handle negative numbers, but you can easily fix that)

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

edit
I just noticed the "recursion" part of the requirement. Well, DP can be rewritten as recursion with memoization, if that's the hard requirement. This would preserve runtime complexity.

edit 2
On groups. You have to assign elements divisible by 3 or 5 to respective groups before you proceed with the algorithm. Let's say, sum of all elements is s, sum of elements divisible by 3 is s3 and sum of elements divisible by 5 but not 3 is s5. In this case, after you assigned those 'special' elements, you have to split the rest that sum in one group is s/2 - s3 and in another s/2 - s5.

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 the function:

canSplit(arr, 0, 0, 0);

Code that would probably get me fired. But will work :D

Entirely recursive, equally deadly.

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);

}

Here is the 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 puting every element into one of the group. If in any combination the two groups are equal it returns true. No loops used and in only one function.

Best for all

edit: Your function takes 4 arguments as input whereas the question gets as input only the array. You have to specify that the desired function could be done using yours with the call split2(0,nums,0,0);

I don't know how fast or slow the following solution is. But precisely it is a recursive backtracking solution, which uses no loops as mentioned 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 it helps.