131:分割回文串
for 遍历字符串
递归切割，切割到字符串尾，单次结束
1 class Solution: 2 def partition(self, s: str) -> List[List[str]]: 3 if(not s): return [] 4 re=[] 5 self.backtracking(s,[],re,0) 6 return re 7 def backtracking(self,s,path,re,index): 8 if(index==len(s)): 9 re.append(path[:]) 10 return 11 for i in range(index,len(s)): 12 strs=s[index:i+1] 13 if(self.bool_hui(strs)): 14 path.append(strs) 15 self.backtracking(s,path,re,i+1) 16 path.pop() 17 else: continue 18 def bool_hui(self,s): 19 if not s: return False 20 lens=len(s) 21 for i in range(lens//2): 22 if(s[i]!=s[lens-i-1]): return False 23 return Truepartition
优化判断字符串是否为回文串：
s[index:i+1]==s[index:i+1][::-1]
all函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False
all(s[i] == s[len(s) - 1 - i] for i in range(len(s) // 2))
93:复原IP地址
链接：93. 复原 IP 地址 - 力扣（LeetCode）
结束条件：每一段IP中.的数量为4时，判断IP长度是否比s长度大4
1 class Solution:
2 def restoreIpAddresses(self, s: str) -> List[str]:
3 if(not s): return []
4 re=[]
5 self.backtracking(s,"",re,0)
6 return re
7 def backtracking(self,s,path,re,index):
8 if(path.count(".")==4):
9 if(len(path)==len(s)+4):
10 re.append(path[:len(path)-1])
11 return
12 for i in range(index,len(s)):
13 strIp=s[index:i+1]
14 if(not self.isvalue(strIp)): return
15 self.backtracking(s,path+strIp+'.',re,i+1)
16 def isvalue(self,strs):
17 if(int(strs)>255): return False
18 if(strs[0]=='0' and len(strs)>1): return False
19 return True
20
21
22
23
restoreIpAddresses
78：子集
结束条件：index=len(nums)，path每append一次，都要放入结果集中，不能再结束时再放
1 class Solution: 2 def subsets(self, nums: List[int]) -> List[List[int]]: 3 if(not nums): return nums 4 re=[[]] 5 self.backtracking(re,[],nums,0) 6 return re 7 def backtracking(self,re,path,nums,index): 8 if(index==len(nums)): 9 return 10 for i in range(index,len(nums)): 11 path.append(nums[i]) 12 self.backtracking(re,path,nums,i+1) 13 re.append(path[:]) 14 path.pop()subsets
90:子集II
数组先排序，排序后，如果i大于index，并且和前一个相等，跳过
1 class Solution: 2 def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: 3 if(not nums): return nums 4 re=[[]] 5 nums.sort() 6 self.backtracking(nums,re,[],0) 7 return re 8 def backtracking(self,nums,re,path,index): 9 if(index==len(nums)): return 10 for i in range(index,len(nums)): 11 if(i>index and nums[i]==nums[i-1]): continue 12 path.append(nums[i]) 13 self.backtracking(nums,re,path,i+1) 14 re.append(path[:]) 15 path.pop()subsetsWithDup
491：非递减子集
em....再来一个试试
1 class Solution: 2 def findSubsequences(self, nums: List[int]) -> List[List[int]]: 3 if(len(nums)<2): return [] 4 re=[] 5 self.backtracking(nums,[],re,0) 6 return re 7 def backtracking(self,nums,path,re,index): 8 #长度为大于2，就放入结果集中 9 if(len(path)>1): re.append(path[:]) 10 #记录当前层哪些元素被用过 11 uset=set() 12 for i in range(index,len(nums)): 13 if((path and path[-1]>nums[i]) or nums[i] in uset): continue 14 uset.add(nums[i]) 15 path.append(nums[i]) 16 self.backtracking(nums,path,re,i+1) 17 path.pop()findSubsequences
46:全排列
for从头开始
1 class Solution: 2 def permute(self, nums: List[int]) -> List[List[int]]: 3 if(not nums): return [] 4 re=[] 5 self.backtracking(nums,[],re) 6 return re 7 def backtracking(self,nums,path,re): 8 if(len(path)==len(nums)): 9 re.append(path[:]) 10 return 11 for i in range(len(nums)): 12 if(nums[i] in path): continue 13 path.append(nums[i]) 14 self.backtracking(nums,path,re) 15 path.pop()permute
47:全排列II
每次递归传入的数组，需要将上一次path添加的元素删除
1 class Solution: 2 def permuteUnique(self, nums: List[int]) -> List[List[int]]: 3 if(not nums): return [] 4 re=[] 5 self.backtracking(nums,[],re,len(nums)) 6 return re 7 def backtracking(self,nums,path,re,lens): 8 if(len(path)==lens): 9 re.append(path[:]) 10 return 11 uset=set() 12 for i in range(len(nums)): 13 if(nums[i] in uset): continue 14 uset.add(nums[i]) 15 path.append(nums[i]) 16 self.backtracking(nums[:i]+nums[i+1:],path,re,lens) 17 path.pop()permuteUnique
==============================================================================================
头痛痛~~想请个假真的是难死，俩领导相互踢皮球，MMD，在自己能力范围内最大限度的为难别人的人都该死，天煞的！！！！再不回消息半夜还给你俩打电话
标签：return,nums,self,len,第六天,path,Leetcode,re,刷题 From： https://www.cnblogs.com/xiaoruru/p/17999763