Write a java function solving this problem utilizing recursion(no DP):

Function: public static int numberOfSolutions(int x, int n)

You are given two integers x and n. x represents the number of rows and n is an integer you will work with. The function must return the number of possible solutions defined by the criteria below:

- You will be adding the numbers to rows

- The numbers must be used in an upward fashion based off of n so e.g. given n = 5, you must use the numbers in the order of 1, 2, 3, 4, 5.

- The numbers will be placed into lines/rows(number represented by x). The catch being that the current number being placed MUST add to a perfect square only with the number in front of it. The first number of each row is excluded from this rule as there is no other number in front of it.

- ALL rows must be populated by at least ONE number in order to be considered a solution.

- Return the number of possible configurations where all the numbers are used and the criteria is met

This may seem confusing but here are some examples to give you a better idea of what is being asked.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Given x=4 rows and n=7:

The "possible solutions" are as follows:

1 3 6

2

4 5

7

---------------

1 3

2 7

4 5

6

--------------

1 3 6

2 7

4

5

---------------

1

2 7

3 6

4 5

The answer of this would be 4 as there are 4 unique combinations that adhere to the criteria.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Uniqueness is in the the number of unique combinations themselves and not their arrangement.

For example:

If

1, 3, 6

2, 7

4, 5

is a possible combination that fits the criteria

then:

4, 5

2, 7

1, 3, 6

would NOT be considered a solution as it is the same as above but simply with a different arrangement.

Therefore the answer to this would only be 1.