C# - recursive char array backtracking


  • 1

    I do pass a redundant variable, currLen, in my recursion but it makes the code a little simpler (I think!).

        public IList<string> GenerateParenthesis(int n) 
        {
            IList<string> list = new List<string>();
            Generate(list, new char[2*n], 0, n, n);
            return list;
        }
        
        public void Generate(IList<string> list, char[] curr, int currLen, int leftRemaining, int rightRemaining)
        {
            if (leftRemaining == 0 && rightRemaining == 0)
            {
                list.Add(new string(curr));
            }
            else
            {
                if (leftRemaining > 0)
                {
                    curr[currLen] = '(';
                    Generate(list, curr, currLen + 1, leftRemaining - 1, rightRemaining);
                }
                if (rightRemaining > leftRemaining)
                {
                    curr[currLen] = ')';
                    Generate(list, curr, currLen + 1, leftRemaining, rightRemaining - 1);
                }
            }
        }
    

Log in to reply
 

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