5.括号生成

题目：

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题思路（回溯）：
        传入数字n表示对数，这个n可以想成括号的分支选项从0到n，n有多少个就有多少个n+1次选择。又要保证传回的括号对是正确的，那么右括号是肯定小于等于左括号的数量，才能够继续往下运行的，所以如果右括号大于左括号就可以直接进行返回，不用再往下执行程序，递归函数内每次只增加一个括号，增加完毕之后交给下一个递归函数执行，如果左括号等于右括号等于n就可以将字符放入返回的列表进行返回

 源代码：

        public IList<string> GenerateParenthesis(int n)
        {
            //定义一个存放正确的字符串的表
            IList<string> result = new List<string>();
            backTracking(n, result, 0, 0, "");
            return result;
        }

        private void backTracking(int n,IList<string> result,int left,int right,string str)
        {
            //如果右括号大于左括号就进行返回
            if (right > left)
                return;

            //如果左括号熟练等于右括号的数量等于n的数量就说明该字符串的是符合规定的，就将他加入返回的List中
            if(left == right && right == n)
            {
                result.Add(str);
                return;
            }

            //如果左括号小于了n就加入（
            if(left < n)
                backTracking(n, result, left + 1, right, str + "(");

            //如果右括号小于右括号就加入 ）
            if (right < left)
                backTracking(n, result, left, right + 1, str + ")");
        }

函数图解：