Ways to Arrange Balls

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion. We will keep track of the next ball we want to add in the line. Initially, we have three options, to begin with. We can start by adding A or B or C. After that, at each step, we have two options. We can find the number of ways to make the required arrangements from the remaining balls. 

Algorithm:  

• We will call a recursive function ‘helper’ that takes all the three integers a, b, c, and a variable ‘nextBall’ as arguments and returns us the total number of ways to arrange the balls in the required fashion.
• Initialize a variable called ‘totalWays’ by 0.
• Call helper function for all possible value of ‘nextBall’ and store the answer in ‘totalWays’, i.e. totalWays = helper(a, b, c, 0) + helper(a, b, c, 1) + helper(a, b, c, 2).
• The algorithm for the helper function will be as follows: 
  Int helper(a, b, c, nextBall):
  A. If ‘a’ or ‘b’ or ‘c’ becomes less than 0, return 0 as we can’t have an arrangement in this case.
  B. Now check,
  • if the ‘nextBall’ is 0, means we have to add a ball of type A.
    • If ‘a’ is 1 and ‘b’ and ‘c’ are 0, return 1 as we have found an arrangement.
    • Else return helper(a - 1, b,  c, 1) + helper(a - 1, b, c, 2).
  • If the ‘nextBall’ is 1, means we have to add a ball of type B.
    • If ‘b' is 1 and ‘a’ and ‘c’ are 0, return 1 as we have found an arrangement.
    • Else return helper(a , b - 1, c, 0) + helper(a, b - 1, c, 2).
  • If the ‘nextBall’ is 2, means we have to add a ball of type C.
    • If ‘c’ is 1 and ‘a’ and ‘b’ are 0, return 1 as we have found an arrangement.
    • Else return helper(a, b, c - 1, 0) + helper(a, b, c - 1, 1).
• Return the ‘totalWays’.

In the recursive approach, there are many overlapping sub-problems. This problem can be solved using memoization.

Algorithm

• The idea is to use memoization.
• Create a 4D lookup table to store the solutions to the subproblems where lookUp[i][j][k][l] denotes the number of ways to arrange the ‘i’ balls of type A,’j’ balls of type B and ‘k’ balls of type C in the required fashion when the next ball we need to add in the line will be known from the value of ‘l’, that is when ‘l’ is 0, we need to place a ball of type ‘A’ and when ‘l’ is 1, we need to place a ball of type B and when ‘l’ is 2, we need to place a ball of type C. Note that ‘l’ can only attain three values, 0, 1, and 2.
• Initialize the table by -1.
• If the value is already computed, return the value.
• Otherwise, compute the value using recursion and store the result in ‘lookUp’ table and return it.

The idea is to use Dynamic Programming. 

We will create a 4D lookup table, DP, to store the solutions to the subproblems where DP[i][j][k][l] denotes the number of ways to arrange the ‘i’ balls of type A,’j’ balls of type B and ‘k’ balls of type C in the required fashion when the next ball we need to add in the line will be known from the value of ‘l’, that is when ‘l’ is 0, we need to place a ball of type ‘A’ and when ‘l’ is 1, we need to place a ball of type B and when ‘l’ is 2, we need to place a ball of type C.

Note that ‘l’ can only attain three values, 0, 1, and 2.

Algorithm

• Initialize the table by 0.
• The detailed algorithm to fill the DP table will be as follows:
  • Loop 1: For i = 0 to a+1:
  • Loop 2: For j = 0 to b+1:
  • Loop 3: For k = 0 to c+1:
  • Loop 4: For l = 0 to 3:
• if the ‘l’ is 0, means we have to add a ball of type A.
  • If i is 1 and j and k are 0, update DP[i][j][k][l] =1 as we have found an  arrangement.
  • Else if i >0, update DP[i][j][k][l] += DP[i-1][j][k][1] + DP[i-1][j][k][2];
• If the ‘l’ is 1, means we have to add a ball of type B.
  • If j is 1 and i and k are 0, update DP[i][j][k][l] =1 as we have found an  arrangement.
  • Else if j > 0, update DP[i][j][k][l] += DP[i][j-1][k][1] + DP[i][j-1][k][2];
• If the ‘l’ is 2, means we have to add a ball of type C.
  • If k is 1 and i and j are 0, update DP[i][j][k][l] =1 as we have found an  arrangement.
  • Else if k > 0, update DP[i][j][k][l] += DP[i][j][k-1[1] + DP[i][j][k-1][2];
• Return (DP[a][b][c][0] + DP[a][b][c][1] + DP[a][b][c][2]) as it is the total no. of ways to arrange the balls in the required manner.