Java solution with recursion.


  • 0
    J

    Explaining code in comments:

    /**
     * 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.
                 */
                valids.add(new String(par));
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.