Easy Short DFS Solution


  • 2
    W

    Easy to understand

    public class Solution
    {
      public IList<string> GenerateParenthesis(int n)
      {
        IList<string> ret = new List<string>();
        DFS(ret, "", n, n);
        return ret;
      }
      
      private static void DFS(IList<string> ans, string cur, int l, int r)
      {
        if ((l == 0) && (r == 0)) ans.Add(cur);
        if (l > 0) DFS(ans, cur + '(', l - 1, r);
        if (l < r) DFS(ans, cur + ')', l, r - 1);
      }
    }
    

  • 0
    L

    Java version:

        public List<String> generateParenthesis(int n) {
            List<String> ret = new ArrayList();
            if(n==0) return ret;
            helper(ret, new StringBuilder(), n, n);
            return ret;
        }
        
        private void helper(List<String> ret, StringBuilder sb, int left, int right){
            if(left==0 && right==0) {
                ret.add(sb.toString());
            }
            if(left>0) {
                int len = sb.length();
                helper(ret, sb.append("("), left-1, right);
                sb.setLength(len);
            }
            if(left<right) {
                int len = sb.length();
                helper(ret, sb.append(")"), left, right-1);
                sb.setLength(len);
            }
        }
    

  • 0
    R

    really short and brilliant answer! thx


Log in to reply
 

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