Simple recursive solution with explantion


  • 1

    Recursion is a good method to solve this problem.

    Suppose after add some parenthesis, there are m left parenthesis and n right parenthesis to add.

    According the value of m and n, there are three kinds of situations.

    (1) m == n

    We can only add left parenthesis

    (2) m < n

    We have two choices, add left parenthesis or right parenthesis.

    When add left parenthesis, we need to judge whether m > 0

    (3) m > n

    This situation is meaningless.

    In Java, the code like this:

    public static List<String> generateParenthesis(int n) {
    	List<String> result = new ArrayList<String>();
    	generateParenthesis(n, n , n, "", result);
    	return result;
    }
    private static void generateParenthesis(int left, int right, int n, 
    		String s, List<String> result) {
    	
    	if (s.length() == n * 2) {
    		result.add(s);
    	} else {
    		if (left == right) {
    			generateParenthesis(left - 1, right, n , s + "(", result);
    		} else if (left < right) {
    			if (left > 0) {
    				generateParenthesis(left - 1, right, n , s + "(", result);
    			}
    			generateParenthesis(left, right - 1, n, s + ")", result);
    		} 
    	}	
    }
    

    It will produces a lot of small Strings, so we can optimize it using Array.

    public static List<String> generateParenthesis(int n) {
    	List<String> result = new ArrayList<String>();
    	char[] str = new char[n * 2];
    	generateParenthesis(n, n , str, 0, result);
    	return result;
    }
    private static void generateParenthesis(int left, int right, char[] str, 
    		int length, List<String> result) {
    	
    	if (length == str.length) {
    		result.add(String.valueOf(str));
    	} else {
    		if (left == right) {
    			str[length] = '(';
    			generateParenthesis(left - 1, right, str, length + 1, result);
    		} else if (left < right) {
    			if (left > 0) {
    				str[length] = '(';
    				generateParenthesis(left - 1, right, str, length + 1, result);
    			}
    			str[length] = ')';
    			generateParenthesis(left, right - 1, str, length + 1, result);
    		} 
    	}	
    }

Log in to reply
 

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