I've m boxes and n balls, each of different size. To give a simple example, let's say we have boxes of size: [10, 50, 20] and balls of size: [20, 10, 30, 10]. It can solved as follows,

Box 0 (Size 10) can store Ball 1 (Size 10) or Ball 3, but let's take Ball 1 for simplicity.

Box 1 (Size 50) can store Ball 0 (size 20) and Ball 2 (size 30)

Box 2 (Size 20) can store Ball 3 (size 10)

To solve this problem, I wrote following is the java code which is solved using sorting and in iterative way,

boolean canBallsFitInBoxes(int [] boxes, int [] balls) {
    Arrays.sort(boxes);
    Arrays.sort(balls);
    int j = 0;
    int i = 0;
    for(; i < balls.length && j < boxes.length;) {
      if(boxes[j] >= balls[i]){
        boxes[j] -= balls[i];
        i  ;
      } else {
        j  ;
      }
      
    }
    
    return i == balls.length;
}

I tested for few cases and above iterative solution works. I might have missed edge cases, happy to hear them correct it.

I tried recursive version by myself, but it works only if given arrays are already sorted or when boxes and arrays can be mapped easily like (boxes: [10, 50, 20] and balls: [10, 20, 30, 10]). Basically, when the order of boxes or balls is jumbled, I'm struggling to find a solution using recursion.

But I'm trying to find a generic way to solve this problem. Any suggestions how can I solve it recursively without explicit sorting?

CodePudding user response：

A brute-force, recursive way of solving the problem would be to take ball n and try to put it into each box. If the ball fits into the current box, recurse into using the next ball, otherwise try the next box.

  public boolean canBallsFitInBoxes(int[] boxes, int[] balls) {
    return fits(boxes, balls, 0);
  }

  private boolean fits(int[] boxes, int[] balls, int currentBall) {
    // All balls used? -> success
    if (currentBall >= balls.length)
      return true;
    for (int currentBox = 0; currentBox < boxes.length; currentBox  ) {
      if (boxes[currentBox] >= balls[currentBall]) {
        boxes[currentBox] -= balls[currentBall];
        if (fits(boxes, balls, currentBall   1))
          return true;
        else
          boxes[currentBox]  = balls[currentBall];
      }
    }
    return false;
  }

If you do not like the success check at the beginning of the recursive method and would rather prefer to check before recursing, you could also use:

  private boolean fits(int[] boxes, int[] balls, int currentBall) {
    for (int currentBox = 0; currentBox < boxes.length; currentBox  ) {
      if (boxes[currentBox] >= balls[currentBall]) {
        boxes[currentBox] -= balls[currentBall];
        if (currentBall   1 >= balls.length || fits(boxes, balls, currentBall   1))
          return true;
        else
          boxes[currentBox]  = balls[currentBall];
      }
    }
    return false;
  }

Feel free to ask, if you do not understand the algorithm.