Backtracing Flashcards
0017 Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
Build a dictionary. Key is number, value is list of alphabet. Use a backtracking recursive function to generate the possible letter combination. def backtracing(comb, i)
for c in table[input[I]): backtracing("", 0)
O(3^Nx4^M)
where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input.
- Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
Use a backtracing recursive function to build all solution.
def backtracing(string, num_left, num_right): if num_left == n and num_right==n: res.append(string)
Add (
if
You can always add “(“, if num_left < n
# Add )
if
You can only add “)” when num_left >num_right
backtracing(“”, 0, 0)
Our complexity analysis rests on understanding how many elements there are in generateParenthesis(n). This analysis is outside the scope of this article, but it turns out this is the n-th Catalan number 1/(n+1)*C(2n, n) which is bounded asymptotically by O(4^n /n^(0.5)n)
- Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2:
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]
Constraints:
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
Each element of candidate is unique.
1 <= target <= 500
duplicate is acceptable so input index.
if the candidates are sorted. You can early break if current candidate is smaller than target.
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
candidates.sort()
def backtracing(comb, i, t):
if t == 0: res.append(comb)
for c in xrange(i, len(candidates)):
if t - candidates[c] < 0:
break
backtracing(comb+[candidates[c]], c, t - candidates[c])
backtracing([], 0, target)
return res
Or iterative
- Combination Sum II
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]
you can’t use the same element twice. so pass c+1
You need to handle duplicate results. So for every position you can’t use the same number. You need to pass the used number.
class Solution(object):
def combinationSum2(self, candidates, target):
“””
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
“””
res = []
candidates.sort()
def backtracing(comb, i, t):
if t == 0: res.append(comb)
prev = None
for c in xrange(i, len(candidates)):
if prev == candidates[c]: continue
if t - candidates[c] < 0: break
backtracing(comb + [candidates[c]], c+1, t - candidates[c])
prev = candidates[c]
backtracing([], 0, target)
return res
Or iterative
- Permutations
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
Remember the edge case.
Use recursive function to go through all permutation.
input permutation and candidate.
Modify the candidate.
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
def backtracing(p, n):
if len(p) == len(nums): res.append(p)
for i in xrange(len(n)):
backtracing(p + [n[i]], n[:i] + n[i+1:])
if not nums:
return []
if len(nums) == 1:
return [nums]
backtracing([], nums)
return res
Iterative insert a new candidate to every position of the exist permutation.
def permute(self, nums):
perms = [[]]
for n in nums:
new_perms = []
for perm in perms:
for i in xrange(len(perm)+1):
new_perms.append(perm[:i] + [n] + perm[i:]) ###insert n
perms = new_perms
return perms
- Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
It is similar to combination II.
sort the candidate. And add a condition that don’t use the same number in the same position.
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
def dfs(prev_per, _nums):
if not _nums:
return [prev_per]
out = []
prev = None
for i in range(len(_nums)):
if _nums[i] != prev:
out += dfs(prev_per+[_nums[i]], _nums[:i]+_nums[i+ 1:])
prev = _nums[i]
return out
if not nums:
return []
if len(nums) == 1:
return [nums]
return dfs([], nums)
- N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Example:
Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."],
["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
recursive to try every column for each row.
In each recursive only try n possible column for the row.
So only n^n try.
And check if this column, diagonal has occur by using set()
diagonal check is set(i+j), set(i-j)
self.solve(board, 0, solutions, vert, diag1, diag2) def solve(self, board, i, solutions, vert, diag1, diag2):
- N-Queens II
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."],
["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
use the same algorithm as 0051. Instead of generate a board, just count the valid board numbers.
- Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character ‘.’.
A sudoku puzzle…
…and its solution numbers marked in red.
Note:
The given board contain only digits 1-9 and the character ‘.’.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.
Use backtracing to try every position. And Using hash map to save the exist value. Hasmap need to update and undo before and after backtracing function.
The improvement is analysis all position possible valid number. And start search from the less possible valid number position.
- Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.
’?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2:
Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence. Example 3:
Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'. Example 4:
Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce". Example 5:
Input:
s = “acdcb”
p = “a*c?b”
Output: false
https://hackmd.io/pLbGG9cQQ7OKmbZaUl1Taw
