I have had this problem for an interview and can't seem to wrap my mind around how to solve it. I have not found any tutorials that explains the logic behind it as well.

Have the function ArrayChallenge(arr), take the array of integers stored in arr which will always contain an even amount of integers, and determine how they can be split into two even sets, then return a string representation of the first set followed by the second set with each integer separated by a comma and both sets sorted in ascending order. The set that goes first is the set with smallest first integer.

For example if arr is [16,22,35,8,20,1,21,11], then your program should output 1,11,20,35,8,16,21,22

[16,22,35,8,20,1,21,11] sum = 134

the sum of 1,11,20,35 is = 67 the sum of 8,16,21,22 is = 67

Also the size of the two arrays are equal to arr.length /2

CodePudding user response：

The problem need not to be sequentially-in-time coded. Make a centrally procedure to solve this knapsack problem, but do not code it yet. Then sort the results, and give the results.

Now should you fail solving, say for time-out, there still is an approach done.

The problem could be further simplified, by using the sum of the array arr, divide it by 2, and search a subarray of this half-sum.

The problem poses some weird restrictions: arr keeps an even number of values (8), the two resulting arrays should have the same even number of values (both 4).

To select to which subarray the i^th value belongs is binary.

So start with a sorted array, cut the solutions when the half is reached.

You could start with 00001111 (half the bits 1) which probably is too big, the following bits would be 00010111, 00011011, 00011101, 00011110, 00101110, ...

Easier would probably simple recursion, with a count upto the half:

// Array arr sorted decreasingly to have less values to try out.
boolean solve(Set<Integer> selectedNumbers, int selectedSum, int index) {
    if (selectedNumbers.size() >= arr.length/2) {
        return sum == arrSum/2;
    }
    if (index > arr.length) {
        return false;
    }
    boolean solved = false;

    // First case: add array element at this index:
    if (selectedSum   arr[index] <= arrSum/2) {
        seplectedNumbers.add(arr[index]);
        arrSum  = arr[index];
        solved = solve(selectedNumbers, arrSum, index   1);
        if (!solved) {
            // No remove(int index), so remove an Object, Integer.
            selectedNumbers.remove(Integer.valueOf(arr[index]));
            arrSum -= arr[index];
        }
    }

    // Second case: do not add array element at this index:
    if (!solved) {
        solved = solve(selectedNumbers, arrSum, index   1);
    }
    return solved;
}

The above of course is a brute force solution. If you are into Operations Research you might find a distribution of those numbers to start with (like the bits mentioned). But time needed and for me my meager math knowledge would prevent that. When solved you might put in a remark should you know a faster solution.

CodePudding user response：

you would use an iteration and traverse the array first. then you make 2 integers. In each iteration cycle, you first check if integer1 is bigger than integer2. then put one number in array1 and add its value to integer1. repeat. if int1 is bigger than int2, you put it in array2 and add the value to int2. in the end, sort the array and you are done. that is how I would solve it. Does this work? I am genuinely interested.