LeetCode Day 25 Backtracking Algorithm (2/6)
Published:
Day before yesterday began suddenly Covid positive, I rest for two days, today no fever continue to study!
Question 1
Find all valid combinations of
knumbers that sum up tonsuch that the following conditions are true:
- Only numbers
1through9are used.- Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
The general idea of using recursion is similar to that of the previous question (LC 77).
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = [] # save results
self.backtracking(n, k, 0, 1, [], result)
return result
def backtracking(self, targetSum, k, currentSum, startIndex, path, result):
if currentSum > targetSum:
return
if len(path) == k:
if currentSum == targetSum:
result.append(path[:])
return
for i in range(startIndex, 9 - (k - len(path)) + 2):
currentSum += i
path.append(i)
self.backtracking(targetSum, k, currentSum, i + 1, path, result)
currentSum -= i
path.pop()
Question 2
17. Letter Combinations of a Phone Number
Given a string containing digits from
2-9inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
It feels like this question has some practical use, but when I think about the nature of it, it’s still a recursive solution
class Solution:
def __init__(self):
self.letterMap = [
"", # 0
"", # 1
"abc", # 2
"def", # 3
"ghi", # 4
"jkl", # 5
"mno", # 6
"pqrs", # 7
"tuv", # 8
"wxyz" # 9
]
self.result = []
self.s = ""
def backtracking(self, digits, index):
if index == len(digits):
self.result.append(self.s)
return
digit = int(digits[index])
letters = self.letterMap[digit]
for i in range(len(letters)):
self.s += letters[i]
self.backtracking(digits, index + 1)
self.s = self.s[:-1]
def letterCombinations(self, digits):
if len(digits) == 0:
return self.result
self.backtracking(digits, 0)
return self.result