List<string> result = new List<string>();
    
    public List<string> generateValidParentheses(int num)
    {
        generate(new List<string>(), numOpen: 0, numClose: 0, num);
        return result;
    }

    private void generate(List<string> list, int numOpen, int numClose, int num)
    {
        // Base case: count of open and close equals num
        if (numOpen == num && numClose == num)
        {
            result.Add(string.Concat(list));
            return;
        }
        // Deadend: num of open less than num of close
        if (numOpen < numClose) return;
        // Recursively generate with open paren if open paren can be added
        if (numOpen < num)
        {
            list.Add("(");
            generate(list, numOpen + 1, numClose, num);
            // Backtrack: remove added paren
            list.RemoveAt(list.Count - 1);
        }
        // Recursively generate with close paren if close paren can be added
        if (numClose < num)
        {
            list.Add(")");
            generate(list, numOpen, numClose + 1, num);
            // Backtrack: remove added paren
            list.RemoveAt(list.Count - 1);
        }
    }