Concise JAVA solution based on backtracking


  • 1

    Time complexity = O(2^n)

    As in each position, there're 2 candidates to put: '(' or ')'. For n positions, there're 2^n possibilities.

    JAVA Code:

    public List<String> generateParenthesis(int n) {
    	List<String>res = new LinkedList<String>();
    	DFS("", n, n, res);
    	return res; 
    }    
    void DFS(String curr, int left, int right, List<String> res) {// left, right: the remaining amount of '(', ')'
    	if (left == 0 && right == 0) {
    	        res.add(curr);
    		return;
    	}
    	if (left > 0)// Check '(': 1) still has '(': '(' can be added without precondition check
    		DFS(curr + "(", left-1, right, res);
    	if (right > 0 && left < right)// Check ')': 1) still has ')'; 2) existing '(' is more than ')'
    		DFS(curr + ")", left, right-1, res);
    }

Log in to reply
 

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