Java DFS 2~3ms solution


  • 0
    C

    DFS based solution.

    public class Solution {
        public List<String> generateParenthesis(int n) {
            
            List<String> list = new LinkedList<String>();
            if (n == 0) {
                list.add("");
                return list;
            }
                
            char[] permu = new char[n*2];
            permu[0] = '(';
            // initialise the permu, so do not need to fill it with ')' every time when need to add to the list
            for (int i = 1; i < permu.length; i ++)
                permu[i] = ')';
            dfs(1, n - 1, permu, list, 1, 0);
            return list;
        }
        
        private void dfs(int startIndex, int count, char[] permu, List<String> list, int gap, int preAvail) {
            
            if (count == 0) {
                // add permu to list
                list.add(new String(permu));
                return;
            }
            
            for (int i = startIndex; i < permu.length - 1; i ++) {
                if (count > 0 && (i - preAvail - 1 <= gap)) {
                    permu[i] = '(';
                    
                    // gap and preVail is to prevent the case such as : (())), or ()())
                    int tempGap = gap;
                    gap ++;
                    gap = gap - (i - preAvail - 1);
                    
                    count --;
                    int temp = preAvail;
                    preAvail = i;
                    // *** every time, start from i + 1
                    dfs(i + 1, count, permu, list, gap, preAvail);
                    permu[i] = ')';
                    count ++;
                    preAvail = temp;
                    gap = tempGap;
                }
            }
        }
    }
    

Log in to reply
 

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