Backtrack.MD

https://leetcode.com/problems/generate-parentheses/

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        result = []
        
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                result.append("".join(S))
                return
            
            if right < left:
                S.append(")")
                backtrack(S, left, right + 1)
                S.pop() 
                
            if left < n:
                S.append("(")
                backtrack(S, left + 1, right)
                S.pop()
            
                
        backtrack([], 0, 0)
        return result

https://leetcode.com/problems/permutations/

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        if len(nums) <= 1:
            return [nums]
        
        result = []
        
        for num in nums:
            new_nums = list(nums)
            new_nums.remove(num)
            permute_rest = self.permute(new_nums)
            
            for perm in permute_rest:
                perm.append(num)
                result.append(perm)
        
        return result

https://leetcode.com/problems/letter-case-permutation/

class Solution(object):
    def letterCasePermutation(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        
        result = []
        n = len(s)
        
        def backtrack(S):
            if len(S) == n:
                result.append("".join(S))
                return
            else:
                c = s[len(S)]
                if c.isdigit():
                    S.append(c)
                    backtrack(S)
                    S.pop()
                else:
                    # lower
                    S.append(c.lower())
                    backtrack(S)
                    S.pop()
                    
                    # upper
                    S.append(c.upper())
                    backtrack(S)
                    S.pop()
                    
                    
        backtrack([])
        return result