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
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
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