Leetcode刷题第八天-回溯

吕从敢

22：括号生成
链接：22. 括号生成 - 力扣（LeetCode）
括号是一对，所以每一次递归结束条件是字符串长度=2*n
有效括号判断：'('个数==')'个数时，当前必须是'('，'('个数==n时，必须是')'，其他情况当前位置遍历两边，既可以是'('又可以是')'

1. 1 class Solution:
2. 2     def generateParenthesis(self, n: int) -> List[str]:
3. 3         if not n :  return []
4. 4         re=[]
5. 5         
6. 6         self.backtracking(2*n,re,"",0)
7. 7         return re
8. 8     def backtracking(self,n,re,path,index):
9. 9         if(len(path)==n):   
10. 10             re.append(path)
11. 11             return
12. 12         for i in range(index,n):
13. 13             num=self.isValid(path,i,n)
14. 14             if(num):    self.backtracking(n,re,path+num,i+1)
15. 15             else:
16. 16                 self.backtracking(n,re,path+'(',i+1)
17. 17                 self.backtracking(n,re,path+')',i+1)
18. 18
19. 19     def isValid(self,path,index,n):
20. 20         count1,count2=path.count('('),path.count(')')
21. 21         if(count1==count2 ):   return '('
22. 22         if(count1==n//2):   return ')'
23. 23         return 0

复制代码

generateParenthesis89:格雷编码
链接：89. 格雷编码 - 力扣（LeetCode）

天哪噜，谁敢信这么个玩意做了一下午
来源:https://www.cnblogs.com/xiaoruru/p/18003636
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！