Divide an array into 2 groups by certain a conditions, using recursion

Question

Given task: "Write function named 'mysplit' that gets an int array and calls a recursive method named 'MySplit'.The function MySplit needs to check if the current array can be divided into 2 groups which follow these conditions:

*The Sum of each group must be equal.

*The occurence of each number is only once in each group(this clause is meant to prevent the user from adding/duplicating numbers in order to get equality between the 2 groups=first clause).

*All the numbers that can be divided by 5 must be in the same group.

*All the numbers that can be divided by 3 (and not by 5) must be in the second group.

I have written this code, but reached a dead end.I fail to fulfil the first 2 clauses of the task and cant think of a way to insert it in my code.

This the code I have written:

public static boolean mySplit(int[] nums)
{
    return MySplit(nums,0,0,0);
}

public static boolean MySplit(int[]arr,int result_5,int result_3,int pointer)//2 groups: 'result_5' & 'result_3' and pointer to iterate through an array
{
    if(arr[pointer]%5==0)
    {
        return MySplit(arr,result_5+arr[pointer],result_3,pointer++);
    }
    else if(arr[pointer]%3==0)
    {
        return MySplit(arr,result_5,result_3+arr[pointer],pointer++);
    }

}

*Edit: **Examples:

mySplit([1,1])==>true

mySplit([1,1,1])==>false

mySplit([2,4,2])==>true

mySplit([5,21,8,15,7])==>true

mySplit([15,10,5])==>false

mySplit([15,8,7])==>true

You should google the task first. Someone already asked this question 6 days ago and there is answer for that: https://stackoverflow.com/questions/50585258/divided-array-according-to-recursion — Dmitry Gorkovets, Jun 03 '18 at 17:54
Possible duplicate of [divided array according to recursion](https://stackoverflow.com/questions/50585258/divided-array-according-to-recursion) — GBlodgett, Jun 03 '18 at 17:55
The linked duplicate question does not have an accepted answer — c0der, Jun 04 '18 at 10:27

score 0 · Answer 1 · answered Jun 04 '18 at 11:52

Note the comments. If more clarification is needed do not hesitate to ask:

public static void main(String[] args) {

    System.out.println(mySplit(1,1));           //true
    System.out.println(mySplit(1,1,1));         //false
    System.out.println(mySplit(2,4,2));         //true
    System.out.println(mySplit(5,21,8,15,7));   //true
    System.out.println(mySplit(15,0,5));        //false
    System.out.println(mySplit(15,8,7));        //true
}

public static boolean mySplit(int...nums)
{
    List<Integer> groupA = new ArrayList<>(); //initialized by all numbers divided by 5
    List<Integer> groupB = new ArrayList<>(); //initialized by all other numbers divided by 3
    List<Integer> groupC = new ArrayList<>(); //initialized by all other numbers

    for(int number : nums) {
        if((number % 5) == 0 ) {
            groupA.add(number);
        }else if ((number % 3) == 0 ) {
            groupB.add(number);
        }else {
            groupC.add(number);
        }
    }

    return mySplit(groupA, groupB, groupC);
}

private static boolean mySplit(List<Integer> groupA, List<Integer> groupB, List<Integer> groupC) {

    if(groupC.size() == 0 ) { //no more numbers to add
        return  sumList(groupA) == sumList(groupB);
    }

    int next = groupC.get(0);
    groupC.remove(0);

    //make a new group A which includes next 
    List<Integer> newGroupA = new ArrayList<>(groupA);
    newGroupA.add(next);

    //make a new group B which includes next 
    List<Integer> newGroupB = new ArrayList<>(groupB);
    newGroupB.add(next);

    //check with new A and B. Make a defensive copy of groupC 
    //to prevent changes in groupC 
    if( mySplit(newGroupA, groupB, new ArrayList(groupC))) {

        return true;
    //check with A and new B
    }else if( mySplit(groupA, newGroupB, new ArrayList(groupC))) {

        return true;
    }

    return false; //equality not found 
}

//sum a list 
private static int sumList(List<Integer> list) {

    /* a pre java 8 version
        int sum = 0;
        for( int i : list ) {  sum += i;}
        return sum;
    */
    return list.stream().mapToInt(Integer::intValue).sum();
}

You can change the signature of mySplit(int...nums) to mySplit(int[] nums) and invoke it by mySplit(new int[]{2,4,2})

Yes. There is nothing wrong with using helper methods (with or without streams). For loops is a valid tool and common in recursive methods [1](https://stackoverflow.com/q/5927369/3992939) [2](https://stackoverflow.com/a/18649326/3992939) [3](https://stackoverflow.com/a/38334953/3992939) [4](https://stackoverflow.com/a/2056276/3992939) — c0der, Jun 05 '18 at 03:23
recursion in an academic setting is different from recursion in a software engineering setting. The whole point of this mental exercise is to formulate the reductive step (i.e. the step where we reduce the size of the inputs remaining to process) in a recursive way. This is more of a hybrid approach since you partly used iteration for that purpose. — Patrick Parker, Jun 05 '18 at 03:33

score 0 · Answer 2 · edited Jun 08 '21 at 06:21

Here is what I came up with:

public static void main(String[] args)
{
    System.out.println(mySplit(new int[] { 1, 1 })); // ==>true

    System.out.println(mySplit(new int[] { 1, 1, 1 })); // ==>false

    System.out.println(mySplit(new int[] { 2, 4, 2 })); // ==>true

    System.out.println(mySplit(new int[] { 5, 21, 8, 15, 7 })); // ==>true

    System.out.println(mySplit(new int[] { 15, 10, 5 })); // ==>false

    System.out.println(mySplit(new int[] { 15, 8, 7 })); // ==>true
}

public static boolean mySplit(int[] nums)
{
    if (nums.length == 0)
        return false;

    return mySplit(nums, 0, 0, 0);
}

private static boolean mySplit(int[] nums, int i, int groupA, int groupB)
{
    if (i == nums.length)
        return groupA == groupB; // At the end, check if the sum of each group is equal.

    if (nums[i] % 5 == 0)
        return mySplit(nums, i + 1, groupA + nums[i], groupB); // All the numbers that can be divided by 5 must be in the same group (Group A).

    if (nums[i] % 3 == 0 && nums[i] % 5 != 0)
        return mySplit(nums, i + 1, groupA, groupB + nums[i]); // All the numbers that can be divided by 3 (and not by 5) must be in the second group (Group B).

    return mySplit(nums, i + 1, groupA + nums[i], groupB) || mySplit(nums, i + 1, groupA, groupB + nums[i]);
}

Divide an array into 2 groups by certain a conditions, using recursion

2 Answers2

Linked