public class Solution {
    public IList<string> GenerateParenthesis(int n)
        {
            List<string> list = new List<string>();
            backtrack(list, "", 0, 0, n);
            return list;
        }

        private void backtrack(List<String> list, String str, int open, int close, int max)
        {

            if (str.Length == max * 2)
            {
                list.Add(str);
                return;
            }

            if (open < max)
            {
                backtrack(list, str + "(", open + 1, close, max);
            }
            if (close < open)
            {
                backtrack(list, str + ")", open, close + 1, max);
            }
        }
}