Clear recursive java solution with only one function


  • 0
    M
    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result=new ArrayList<String>();
            //Edge case;
            if(n==0) return result;
            if(n==1){
                result.add("()");
                return result;
            }
    
            //Add string in the form of {i parenthesis}{n-i parenthesis}
            for(int i=1; i<n; i++){
                List<String> part1=generateParenthesis(i);
                List<String> part2=generateParenthesis(n-i);
                for(int j=0; j<part1.size(); j++)
                    for(int k=0; k<part2.size(); k++){
                        if(result.indexOf(part1.get(j)+part2.get(k))==-1)//Note that ()()(), for example,  would be counted twice without this verification, since it belongs to {1}{2} and {2}{1} at the same time
                            result.add(part1.get(j)+part2.get(k));
                    }
                        
            }
            //Add string in the form of "("{n-1 parenthesis}")"
            List<String> mid=generateParenthesis(n-1);
            for(int i=0; i<mid.size(); i++)
                result.add("("+mid.get(i)+")");
    
            return result;
        }
    }

Log in to reply
 

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