A binary-based solution in Java


  • 0
    Y

    Here is my solution by considering the possible results as binary numbers. The idea is simple. Suppose '(' represents 1 and ')' represents 0. The possible results are located in the range [2^(2n-1), 2^(2n)-2]. We then check every number in this range (similar to Problem 20 Valid Parenthese).

    Well, the problem of this approach is that n cannot be too large. Anyway, the code below is still accepted by OJ.

    public class Solution {
        public List<String> generateParenthesis(int n) {
            ArrayList<String> list = new ArrayList<String>();
    		
    		for (int i = (int)Math.pow(2, 2*n-1); i < (int)(Math.pow(2, 2*n)-1); i = i + 2) {
    			Stack<Character> stack = new Stack<Character>();
    			StringBuffer buffer = new StringBuffer();
    			int tmp = i;
    			while (tmp > 0) {
    				if (tmp % 2 == 1)	{	// 1 represents '(', 0 represents ')'
    					buffer.append(')');
    					if (stack.isEmpty() || stack.pop() != ')') {	
    						break;
    					}
    				}
    				else {
    					buffer.append('(');
    					stack.push(')');
    				}
    				tmp = tmp / 2;
    			}
    			if (stack.isEmpty() && buffer.length() == 2 * n) {
    				list.add(buffer.toString());
    			}
    		}
    		
    		return list;
        }
    }

Log in to reply
 

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