Article directory
- 1. Combination
- 2. Combined Sum III
- 3. Alphabet combination of phone number
- 4. Combined sum
- 5. Combined Sum II
- 6. Split palindrome string
- 6. Restoring the IP address
- 7. Subset
1. Combination
77. Combination
recursion + pruning
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
path = []
def backtracking(n:int, k:int, startint:int):
if len(path)==k:
result.append(path.copy())
return
for i in range(startint, n-(k-len(path)) + 1 + 1):
path.append(i)
backtracking(n,k,i+1)
path. pop()
backtracking(n, k, 1)
return result
2. Combined sum III
216. Combined sums III
Pruning: range value pruning in for loop, sum size pruning
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = []
path = []
def backtracking(k:int, n:int, startint:int, sum:int):
if sum > n:
return
if len(path)==k:
if sum==n:
result.append(path.copy())
return
for i in range(startint,11-(k-len(path))):
path.append(i)
sum + = i
backtracking(k, n, i + 1, sum)
path. pop()
sum -= i
backtracking(k, n, 1, 0)
return result
3. The combination of letters of the phone number
17. Alphabet combinations for phone numbers
The width of the backtracking binary tree is the number of letters corresponding to each number, and the depth is the length of digits.
class Solution:
def __init__(self) -> None:
self.path = ""
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
result = []
dic = ["", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
def backtracking(digits:str, startint:int):
if len(self.path)==len(digits):
result.append(self.path)
return
for i in range(len(dic[int(digits[startint])])):
self.path += dic[int(digits[startint])][i]
backtracking(digits, startint + 1)
self.path = self.path[:-1]
backtracking(digits, 0)
return result
4. Combined sum
39. Combined sum
The termination condition is increased: sum>target is return
Pruning: sum + i > target ends the loop
Note: candidates should be sorted
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates = sorted(candidates)
result = []
path = []
def backtracking(candidates: List[int], target: int, sum:int, startint:int):
if sum > target: return
elif sum == target:
result.append(path.copy())
return
else:
for i in range(startint,len(candidates)):
if sum + candidates[i]>target: return
path.append(candidates[i])
sum + = candidates[i]
backtracking(candidates, target, sum, i)
sum -= candidates[i]
path. pop()
backtracking(candidates, target, 0, 0)
return result
5. Combined sum II
40. Combined Sum II
Pruning: Use the used array to cut off the horizontal branches (not the same branches as the previous one), and keep the vertical branches
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
path = []
used = [0]*len(candidates)
def backtracking(candidates: List[int], target: int, sum:int, startint:int):
if sum > target: return
elif sum == target:
result.append(path.copy())
return
for i in range(startint, len(candidates)):
if sum + candidates[i]>target: return
if i>0 and used[i-1]==0 and candidates[i-1]==candidates[i]: continue
path.append(candidates[i])
sum + = candidates[i]
used[i] = 1
backtracking(candidates, target, sum, i + 1)
used[i] = 0
sum -= candidates[i]
path. pop()
backtracking(sorted(candidates), target, 0, 0)
return result
6. Split palindrome
131. Split palindrome
Horizontal: target string length, i(startint + 1:len(s) + 1)
Vertical: start position >= target string length
Note: the start and end position of the slice
class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s: return []
result = []
path = []
def isPalindrome(s:str):
for i in range(int(len(s)/2)):
if s[i]!=s[len(s)-i-1]:
return False
return True
def backtracking(s:str, startint:int):
if startint>=len(s):
result.append(path.copy())
return
for i in range(startint + 1,len(s) + 1):
t = s[startint:i]
if isPalindrome(t):
path.append(t)
backtracking(s, i)
path. pop()
backtracking(s,0)
return result
6. Restore IP address
93. Restoring IP address
Horizontal: The length of the target string (startint, len(s)) exceeds 3 digits and is illegal
Vertical: 3 (the last paragraph judges whether it is legal)
Note: judging illegal characters
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
if len(s) > 12: return []
result = []
def isvalid(s: str, start: int, end: int):
if start>=end: return False
if s[start]=='0' and (end-start)>1: return False
if not 0<=int(s[start:end])<=255: return False
return True
def backtracking(s:str, startint:int, path:str, flag:int):
if flag == 3:
if isvalid(s,startint,len(s)):
path += s[startint:]
result. append(path)
return
for i in range(startint,len(s)):
if isvalid(s, startint, i + 1):
t = t = s[startint:i + 1]
path = path + t + "."
backtracking(s, i + 1, path, flag + 1)
path = path[:-len(t)-1]
backtracking(s,0,"",0)
return result
7. Subset
78. Subset
Each node is added, not the leaf node
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
def backtracking(nums: List[int], startint:int):
result.append(path.copy())
if startint==len(nums):
return
for i in range(startint, len(nums)):
path.append(nums[i])
backtracking(nums, i + 1)
path. pop()
backtracking(nums,0)
return result