My accepted JAVA solution


  • 31
    P

    For 2, it should place one "()" and add another one insert it but none tail it,

    '(' f(1) ')' f(0)

    or add none insert it but tail it by another one,

    '(' f(0) ')' f(1)

    Thus for n, we can insert f(i) and tail f(j) and i+j=n-1,

    '(' f(i) ')' f(j)

    public List<String> generateParenthesis(int n) {
    	List<String> result = new ArrayList<String>();
    	if (n == 0) {
    		result.add("");
    	} else {
    		for (int i = n - 1; i >= 0; i--) {
    			List<String> insertSub = generateParenthesis(i);
    			List<String> tailSub = generateParenthesis(n - 1 - i);
    			for (String insert : insertSub) {
    				for (String tail : tailSub) {
    					result.add("(" + insert + ")" + tail);
    				}
    			}
    
    		}
    	}
    	return result;
    }

  • 0
    J
    public class Solution {
        private List<String> list;
        public List<String> generateParenthesis(int n) {
            list = new ArrayList<String>();
            for (int i=0;i<(1<<(n*2));i++) {
                genAllSubs(i,n*2);
            }
            return list;
        }
        public void genAllSubs (int S, int n) {
            StringBuilder sb = new StringBuilder();
            int tag = 0;
            for (int i=0; i<n; i++) {
                if ( (S&(1<<i)) != 0) {
                    sb.append("(");
                    tag++;
                } else {
                    sb.append(")");
                    tag--;
                }
                if(tag < 0)break;
            }
            if(tag == 0)
                list.add(sb.toString());
        }
    }
    

    My solution with subsets. But this implement seems pretty slow. Any improvement?


  • 1
    A

    I think you can add a cache to improve performance; so for the same n, you only need to calculate once.


  • 0
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 0
    M
    	public static List<String> generateParenthesis1(int n) {
    
    	List<String> result = new ArrayList<String>();
    	if (n == 0) {
    		result.add("");
    		return result;
    	}
    
    	for (int i = 0; i < n; i++) {
    		List<String> t1 = generateParenthesis1(n - i - 1);
    		List<String> t2 = generateParenthesis1(i);
    		System.out.println("t1 is");
    		System.out.println(t1);
    
    		System.out.println("t2 is");
    		System.out.println(t2);
    		for (int j = 0; j < t1.size(); j++) {
    			for (int k = 0; k < t2.size(); k++) {
    				String temp = "(" + t1.get(j) + ")" + t2.get(k);
    				result.add(temp);
    			}
    		}
    	}
    
    	return result;
    }
    

    I have a similar solution, but I keep getting time limit exceeded. The only thing I don't have is the if else condition, which should not matter. Anyone notice something on my code?


  • 0

    It's better to use dynamic programming to avoid computing result for same i.


  • 1
    R

    tell me time complexity?


  • 0
    B

    delete your System.out.println code might help


Log in to reply
 

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