Split array into two even sets of integers, each so that both sets add up to the same number

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

This answer is similar in spirit to that of Joop Eggen. It implements the (smallish) optimization of checking both selectedTotal and discardedTotal to abort a branch if it exceeds the goal (note that this assumes that all values are positive; if this is not the case, and the smallest value is, say, x < 0, you would just have to add -x to all values, run the algorithm, and substract -x from the answers).

The output is exactly as specified by the original post - and since it is only generated when a full solution is found, this code should be faster than algorithms where values are being constantly added and removed from a partial answer, such as Joop's (selectedNumbers.add followed by selectedNumbers.remove when it turns out not to work; set operations may be fast, but not performing them is even faster!).

public class Main {
    public static boolean search(int[] values, int goal, int index,
                                int selectedTotal, int discardedTotal,
                                List<Integer> selected, List<Integer> discarded) {
        if (selected.size() == values.length/2 &&
                discarded.size() == values.length/2) {
            return selectedTotal == goal;
        }
        if (selectedTotal > goal ||
                discardedTotal > goal ||
                index == values.length) {
            return selectedTotal == goal;
        }

        // try selecting value at index ...
        if (selected.size() < values.length/2 &&
                search(values, goal, index + 1,
                    selectedTotal + values[index], discardedTotal,
                    selected, discarded)) {
            selected.add(values[index]);
            return true;
        }

        // ... and, if that did not work, try discarding value at index
        if (discarded.size() < values.length/2 &&
                search(values, goal, index + 1,
                    selectedTotal, discardedTotal + values[index],
                    selected, discarded)) {
            discarded.add(values[index]);
            return true;
        }
        return false;
    }

    public static List<Integer> solve(int[] values) {
        Arrays.sort(values);
        int goal = IntStream.of(values).sum() / 2;
        List<Integer> selected = new ArrayList<>();
        List<Integer> discarded = new ArrayList<>();
        if ( ! search(values, goal, 0,
                0, 0, selected, discarded)) {
            throw new IllegalArgumentException("This puzzle cannot be solved");
        }
        Collections.reverse(selected);
        Collections.reverse(discarded);
        selected.addAll(discarded);
        return selected;
    }

    public static void main(String[] args) {
        System.out.println(solve(new int[] {16,22,35,8,20,1,21,11}));
    }
}

Answer 4

const arr = [16, 22, 35, 8, 20, 1, 21, 11];

function accumulate(arr, first, last) {
  let init = 0;
  for (let i = first; i < last; i++) {
    init = init + arr[i];
  }
  return init;
}


function combinationUtil(arr, half, start, end,
  index, n, sum) {

  // Current combination is ready to
  // be printed, print it
  if (index == n / 2) {
    let curr_sum = accumulate(half, 0, n / 2);
    return (curr_sum + curr_sum == sum);
  }

  // Replace index with all possible elements.
  // The condition "end-i+1 >= n/2-index" makes
  // sure that including one element at index
  // will make a combination with remaining
  // elements at remaining positions
  for (let i = start; i <= end && end - i + 1 >= n / 2 - index; i++) {
    half[index] = arr[i];
    if (combinationUtil(arr, half, i + 1, end,
        index + 1, n, sum))
      return true;
  }
  return false;
}

function evenSlpit(arr) {
  const n = arr.length;
  arr.sort((a, b) => a - b);
  const sum = arr.reduce((acc, red) => acc + red, 0);

  if (n % 2 != 0)
    return false;

  // If sum of array is not even.
  if (sum % 2 != 0)
    return false;

  // A temporary array to store all
  // combination one by one let k=n/2;
  let half = [];

  // Print all combination using temporary
  // array 'half[]'
  const res = combinationUtil(arr, half, 0, n - 1,
    0, n, sum);
  if (res) {
    const temp = [...half];
    const otherHalf = [];

    for (let i = 0; i < arr.length; i++) {
      if (temp.includes(arr[i])) {
        const index = temp.indexOf(arr[i]);
        temp.splice(1, index);
      } else {
        otherHalf.push(arr[i]);
      }
    }
    return [...half.sort((a, b) => a - b), ...otherHalf.sort((a, b) => a - b)]
  }
  return -1
}

console.log(evenSlpit(arr))
console.log(evenSlpit([1,2,3,4]))
console.log(evenSlpit([1,7,8,3,5,4]));