Backtracking¶
Table of Contents¶
- 17. Letter Combinations of a Phone Number (Medium)
- 77. Combinations (Medium)
- 46. Permutations (Medium)
- 39. Combination Sum (Medium)
- 52. N-Queens II (Hard)
- 22. Generate Parentheses (Medium)
- 79. Word Search (Medium)
17. Letter Combinations of a Phone Number¶
"""
- Return all possible letter combinations that the number could represent.
"""
from typing import List
# Backtracking
def letterCombinations(digits: str) -> List[str]:
letter_map = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
n = len(digits)
if n == 0:
return []
res = []
def dfs(idx, path):
if idx == n:
res.append(path)
return None
letters = letter_map[digits[idx]]
for i in range(len(letters)):
dfs(idx + 1, path + letters[i])
dfs(0, "")
return res
if __name__ == "__main__":
assert letterCombinations("23") == [
"ad",
"ae",
"af",
"bd",
"be",
"bf",
"cd",
"ce",
"cf",
]
77. Combinations¶
from itertools import combinations
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
"""Backtracking: O(k * C(n,k)) time, O(k) space.
Prune by ensuring remaining elements suffice for k.
"""
res = []
def bt(start: int, path: List[int]) -> None:
if len(path) == k:
res.append(path[:])
return
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
bt(i + 1, path)
path.pop()
bt(1, [])
return res
def combineItertools(self, n: int, k: int) -> List[List[int]]:
"""Itertools: O(k * C(n,k)) time, O(k) space.
Leverage stdlib combinations generator.
"""
return [list(c) for c in combinations(range(1, n + 1), k)]
def test_combine():
s = Solution()
for fn in (s.combine, s.combineItertools):
assert sorted(fn(4, 2)) == sorted(
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
)
assert sorted(fn(4, 3)) == sorted([[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]])
assert fn(1, 1) == [[1]]
46. Permutations¶
from typing import List
# Backtracking
def permute(nums: List[int]) -> List[List[int]]:
n = len(nums)
path, res = [], []
used = [False for _ in range(n)]
def dfs(x: int):
if x == n:
res.append(path[:])
return
for i in range(n):
if used[i]:
continue
used[i] = True
path.append(nums[i])
dfs(x + 1)
path.pop()
used[i] = False
dfs(0)
return res
print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3],
# [2, 3, 1], [3, 1, 2], [3, 2, 1]]
39. Combination Sum¶
from typing import List
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
res, path = [], []
def dfs(total, start):
if total > target:
return
if total == target:
res.append(path.copy())
return
for i in range(start, n):
total += candidates[i]
path.append(candidates[i])
dfs(total, i)
total -= candidates[i]
path.pop()
dfs(0, 0)
return res
if __name__ == "__main__":
print(combinationSum([2, 3, 5], 8))
# [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
print(combinationSum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]
52. N-Queens II¶
22. Generate Parentheses¶
from typing import List
# Backtracking
def generateParenthesis1(n: int) -> List[str]:
path, res = [], []
def dfs(openN, closeN):
if openN == closeN == n:
res.append("".join(path))
return
if openN < n:
path.append("(")
dfs(openN + 1, closeN)
path.pop()
if closeN < openN:
path.append(")")
dfs(openN, closeN + 1)
path.pop()
dfs(0, 0)
return res
# Backtracking
def generateParenthesis2(n: int) -> List[str]:
m = n * 2
res, path = [], [""] * m
def dfs(i, left):
if i == m:
res.append("".join(path))
return
if left < n:
path[i] = "("
dfs(i + 1, left + 1)
if i - left < left:
path[i] = ")"
dfs(i + 1, left)
dfs(0, 0)
return res
if __name__ == "__main__":
print(generateParenthesis1(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']
print(generateParenthesis2(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']
79. Word Search¶
from typing import List
def exist(board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
path = set()
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i] or (r, c) in path:
return False
path.add((r, c))
for dr, dc in dirs:
if dfs(r + dr, c + dc, i + 1):
return True
path.remove((r, c))
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
board = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"],
]
word = "ABCCED"
print(exist(board, word)) # True