Accepted Java recursion solution, easy to understand


  • 2
    Y

    The idea is to count unmatched left parenthesis.
    When there is no unmatched left "(", the next one has to be "(".
    When unmatched "(" count is less than unfilled slots, it can be either "(" or ")".IMPORTANT, In this case, we need to remember the position.
    When unmatched "(" count is equal to remained slots, it has to be ")".

    I am new to java.

    public static List<String> generateParenthesis(int n)
    {
    List<String> ret = new ArrayList<>();
    if(n == 0)
    return ret;

        StringBuilder sbr = new StringBuilder();
        generateParenthesisHelper(ret, sbr, 0, 2 * n);
        return ret;
    }
    
    private static void generateParenthesisHelper(List<String> strs, StringBuilder sb, int unmatchedLeft, int targetLength)
    {
        if(sb.length() == targetLength)
        {
            strs.add(sb.toString());
        }
        else
        {
            if(unmatchedLeft == 0)
            {
                sb.append('(');
                generateParenthesisHelper(strs, sb, unmatchedLeft + 1, targetLength);
            }
            else
            {
                if(unmatchedLeft < (targetLength - sb.length()))
                {
                    int tmp = sb.length();
                    sb.append('(');
                    generateParenthesisHelper(strs, sb, unmatchedLeft + 1, targetLength);
                    sb.setLength(tmp);
                    sb.append(')');
                    generateParenthesisHelper(strs, sb, unmatchedLeft - 1, targetLength);
                }
                else
                {
                    sb.append(')');
                    generateParenthesisHelper(strs, sb, unmatchedLeft - 1, targetLength);
                
                }
            }
        }
    }

  • 0
    M

    public class Solution {
    /*
    * ((( )))
    * (( )) ()
    * () (( ))
    * ()()()
    *
    * http://blog.csdn.net/yutianzuijin/article/details/13161721#comments
    * http://www.tuicool.com/articles/BRZjmqA
    * 用dfs思想做递归就好了,记好了先写base case,left,right走过一遍了,可以把这个String加进list
    * 回溯法是对解空间的深度优先搜索,在一般情况下使用递归函数来实现回溯法比较简单
    */
    public List<String> generateParenthesis(int n) {
    if(n<=0)
    return null;
    ArrayList<String> list = new ArrayList<String>();
    String str = new String();
    dfs(list,str,n,n);
    return list;
    }
    public void dfs(ArrayList<String> list, String str, int left, int right){
    if(left>right)
    return; //problem with ")("
    if( left==0 && right==0 )
    {
    list.add(str);
    }
    if(left>0)
    dfs(list,str+"(",left-1,right);
    if(right>0)
    dfs(list, str+")",left,right-1);
    }
    }


Log in to reply
 

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