【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成

class Solution:

    def letterCasePermutation(self, S: str) -> List[str]:

        def DFS(s_list, index):

            if index == len(s_list):

                res.append(''.join(s_list))

                return 

            # 未修改当前字符(字母或者数字)的一条分支  

            DFS(s_list, index + 1) 

            # 修改当前字母的的另一条分支

            if s_list[index].isalpha():

                s_list[index] = chr(ord(s_list[index]) ^ 32)

                DFS(s_list, index + 1)

        res = []

        S = list(S)

        DFS(S, 0)

        return res

# 回溯

class Solution:

    def permutation(self, s: str) -> List[str]:

        def backtrack(s, cur_s):

            if len(cur_s) == len(s):

                res.append(cur_s)

                return

            for i in range(len(s)):

                if i > 0 and s[i] == s[i-1] and visited[i-1] == False:

                    continue

                if visited[i] == False:

                    visited[i] = True

                    backtrack(s, cur_s + s[i])

                    visited[i] = False

        res = []

        visited = [False for _ in range(len(s))]

        s = ''.join(sorted(list(s)))

        backtrack(s,'')

        return res

class Solution:

    def generateParenthesis(self, n: int) -> List[str]:

        res = []

        def generator(left, right, s):

            if left == n and right == n:

                res.append(s)

                return

            if left < n:

                generator(left+1, right, s + '(')

            if left > right:

                generator(left, right+1, s + ')')

        generator(0,0,'')

        return res