Optimizing the back-tracking solution in C#

  • 0

    public class Solution {
    private void Backtrack(List<String> list, LinkedList<char> charList, int open, int close, int max){

        if(charList.Count == max*2){
            char[] buffer = new char[charList.Count];
            int i=0;
            foreach(char item in charList){
                buffer[i++] = item;
            list.Add(new string(buffer));
        if(open < max){
            Backtrack(list, charList, open+1, close, max);
        if(close < open){
            Backtrack(list, charList , open, close+1, max);
    public IList<string> GenerateParenthesis(int n) {
        List<String> list = new List<String>();
        LinkedList<char> charList = new LinkedList<char>();
        Backtrack(list, charList, 0, 0, n);
        return list;    


    I planned around with Yan's solution, which was nice, but made some optimizations, and, also, ported it to C#. I removed the string concats, and, also, used a LinkedList<char> instead of string. It is smoking fast! Give it a try.

Log in to reply

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