# Java solution with recursion.

``````/**
* A way to do a parenthesis test, is using a sum, adding 1 when
* parenthesis opens or -1 when parenthesis closes. At any time
* if the sum is negative, it is not worthy to check the rest of parenthesis,
* it is not valid. If you reach EOF and sum is not equals to Zero, it is not
* valid.
*
* Taking advantage of this parenthesis test method, we can create an algorithm
* which only time complexity is O(R) where R is the amount of results.
* If there is no feasible results, we should not continue.
*/
class Solution {

public List<String> generateParenthesis(int n) {
List<String> valid = new ArrayList<String>();

/*
* Creating an array with enough space to store all posible combinations.
* We can achieve the same concatenating Strings, but we know in advance
* that the length of the valid String will be the double of N, and we
* can avoid creating Strings for each recursive calls and just when
* we have a valid result.
*
* Position is zero because it will be appended in the first position
*
* Sum is 1 because we are openning parenthesis. At this point we know
* that we dont have to test with ')' because it is the first character
*/
test(new char[n * 2], '(', 0, 1, valid);
return valid;
}

/**
* find every valid combination, only proceed when is viable.
*
* @param par When reach the final position, this char array contains
*            a valid combination.
* @param next Next parenthesis to append in par array.
* @param position position where parenthesis will be appended.
* @param sum +1 will be added when appending '(' -1 when papending ')'.
* @param valids This contains the list of valid combinations.
*/
public void test(char[] par, char next, int position, int sum, List<String> valids) {

/*
* Any time sum is negative, we know is not valid.
* If we reach final position, sum has to be zero to be valid.
*/
if (sum < 0 || sum > 0 && position == par.length - 1)
return;

par[position] = next;

if (position < par.length - 1) {
/*
* We have not reach the final position we proceed with 2 posible
* paths: Openning another, or closing, sum adds 1 when openning,
* -1 when closing.
*/
test(par, '(', position + 1, sum + 1, valids);
test(par, ')', position + 1, sum - 1, valids);
} else {
/*
* This is the final position, since first if-statement was false
* the result is valid.
*/