Backtracking Flashcards
- Generate Parentheses
Solved
Medium
Topics
Companies Amazon
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Constraints:
1 <= n <= 8
https://leetcode.com/problems/generate-parentheses/description/
Trick: Add open when you can, add closed when you can
We do not need to pop stuff as we do not modify the original value, we just send a modified version to the next call.
class Solution(object):
def generateParenthesis(self, n):
“””
:type n: int
:rtype: List[str]
“””
ret = []
def rec(val, numopen, numclosed):
if numopen == numclosed == n:
ret.append(““.join(val))
return
if numopen < n:
rec(val + ['('], numopen+1, numclosed)
if numclosed < numopen:
rec(val + [')'], numopen, numclosed+1)
rec([], 0, 0)
return ret
- Subsets
Medium
Given an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.
class Solution(object):
def subsets(self, nums):
“””
:type nums: List[int]
:rtype: List[List[int]]
“””
output = [[]]
for num in nums:
output += [cur + [num] for cur in output]
return output
Backtracking
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subsets = []
def dfs(i):
if i >= len(nums):
res.append(subsets.copy())
return
subsets.append(nums[i])
dfs(i+1)
subsets.pop()
dfs(i+1)
dfs(0)
return res
- Combination Sum
Medium
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40
https://leetcode.com/problems/combination-sum/description/
class Solution(object):
def combinationSum(self, candidates, target):
“””
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
“””
output = []
def rec(nums, idx):
if nums and sum(nums) == target:
output.append(nums[:])
return
if (idx == len(candidates)) or (nums and sum(nums) > target):
return
rec([candidates[idx]] + nums, idx)
rec(nums, idx + 1)
rec([], 0)
return output
- Permutations
Medium
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
https://leetcode.com/problems/permutations/description/
Note the use of Set here, otherwise for each call we have to do n operations.
~~~
class Solution(object):
def permute(self, nums):
“””
:type nums: List[int]
:rtype: List[List[int]]
“””
output = []
seen = set()
def rec(perms):
if len(perms) == len(nums):
output.append(perms[:])
return
for num in nums:
if num not in seen:
seen.add(num)
rec([num] + perms)
seen.remove(num)
rec([])
return output ```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
output = [[]]
for n in nums:
temp = []
for p in output:
for i in range(len(p)+1):
temp.append(p[:i] + [n] + p[i:])
output = temp
return output
- Permutations II
Solved
Medium
Topics
Companies
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
https://leetcode.com/problems/permutations-ii/description/
from collections import Counter
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
output = []
counts = Counter(nums)
def rec(perms):
if len(perms) == len(nums):
output.append(perms[:])
return
# Use the unique nums to iterate. This way you accurately track if its been used or not.
for num in counts.keys():
if counts[num]:
counts[num] -= 1
rec([num] + perms)
counts[num] += 1
rec([])
return output
- Subsets II
Solved
Medium
Topics
Companies
Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
https://leetcode.com/problems/subsets-ii/description/
The non sort does the same thing, if we notice, we do not make a call without the number if it’s already in the set.
We know that if it’s already in the set, the first occurance, will make the call without itself.
This will make sure to include all subsets.
~~~
et 1123
1 1 2 3
1 1 2
1 1 3
1 2– skip this chain as it will be repeated later.
1
1 2 3 - here is the chain we skipped earlier.
1 2
1 3
1
2 3
2
3
~~~
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
output = []
def rec(subsets, idx):
if idx == len(nums):
output.append(subsets[:])
return
rec([nums[idx]] + subsets, idx + 1)
if nums[idx] not in subsets:
rec(subsets, idx + 1)
rec([], 0)
return output
Other way is to sort the nums and if the previous is the same, skip.
add subsets so far each iteration to the output.
Each call go over the all the nums from idx to len(nums) where idx is incremented for each call.
Only the first non dup number will be used if its not the first time using it (i != idx)
eg.
~~~
1123
for ease of example first 1 is 1a and secondis 1b
1a
1a 1b
1a 1b 2
1a 1b 2 3
1a 1b 3
1a 1b
1a 2
1a 2 3
1a 3
1b - Skip as 1b is not idx (0) and its == 1a (i-1 loc)
2 3
2
3
~~~
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
output = []
nums.sort()
def rec(subsets, idx):
output.append(subsets[:])
if idx == len(nums):
return
for i in range(idx, len(nums)):
if i != idx and nums[i-1] == nums[i]:
continue
rec(subsets + [nums[i]], i+1)
rec([], 0)
return output
- Word Search
Solved
Medium
Topics
Companies
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
Output: true
Example 2:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
Output: true
Example 3:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
Output: false
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board?
https://leetcode.com/problems/word-search/
from collections import deque, Counter
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
movements = [[0,1], [-1,0], [1,0], [0,-1]]
seen = set()
rows = len(board)
cols = len(board[0])
# If matrix smaller than word
if rows * cols < len(word):
return False
chars = {c for row in board for c in row}
# If board does not have all the characters in the word
if not chars.issuperset(set(word)):
return False
# if the board char counts are not same as word's char count
board_counts = Counter(c for row in board for c in row)
counts_word = Counter(word)
if not counts_word <= board_counts:
return False
word = word if counts_word[word[0]] < counts_word[word[-1]] else word[::-1]
def dfs(ri, ci, word):
if not word:
return True
seen.add((ri,ci))
for rm, cm in movements:
rn, cn = ri + rm, ci + cm
if rn in range(rows) and cn in range(cols) and board[rn][cn] == word[0] and (rn, cn) not in seen:
found = dfs(rn, cn, word[1:])
if found:
return True
seen.remove((ri, ci))
return False
for r in range(rows):
for c in range(cols):
if board[r][c] == word[0]:
found = dfs(r,c, word[1:])
if found:
return True- Palindrome Partitioning
Medium
Given a string s, partition s such that every
substring
of the partition is a
palindrome
. Return all possible palindrome partitioning of s.
Example 1:
Input: s = “aab”
Output: [[“a”,”a”,”b”],[“aa”,”b”]]
Example 2:
Input: s = “a”
Output: [[“a”]]
Constraints:
1 <= s.length <= 16 s contains only lowercase English letters.
https://leetcode.com/problems/palindrome-partitioning/description/
class Solution:
def partition(self, s: str) -> List[List[str]]:
output = []
# Slower
def _isPalindrome(word):
l = 0
r = len(word) - 1
while l < r:
if word[l] != word[r]:
return False
l+=1
r-=1
return True
# This is faster, possibly optimized by python.
def isPalindrome(word):
return word == word[::-1]
def rec(i, palins):
if i == len(s):
output.append(palins[:])
return
for idx in range(i, len(s)):
if isPalindrome(s[i:idx+1]):
rec(idx+1, palins + [s[i:idx+1]])
rec(0, [])
return output
Using Dynamic Programming
class Solution:
def partition(self, s):
res = []
dp = [[False] * len(s) for _ in range(len(s))]
def dfs(pals, start):
if start >= len(s):
res.append(pals[:])
return
for end in range(start, len(s)):
if s[start] == s[end] and (end-start <= 2 or dp[start+1][end-1]):
dp[start][end] = True
dfs(pals + [s[start:end+1]], end+1)
dfs([], 0)
return res
- Letter Combinations of a Phone Number
Solved
Medium
Topics
Companies
Given a string containing digits from 2-9 inclusive, 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.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
Example 2:
Input: digits = “”
Output: []
Example 3:
Input: digits = “2”
Output: [“a”,”b”,”c”]
Constraints:
0 <= digits.length <= 4 digits[i] is a digit in the range ['2', '9'].
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
letter_map = {
“2”: “abc”,
“3”: “def”,
“4”: “ghi”,
“5”: “jkl”,
“6”: “mno”,
“7”: “pqrs”,
“8”: “tuv”,
“9”: “wxyz”
}
output = []
def build(i, comb):
if i == len(digits):
output.append(comb[:])
return
for c in letter_map[digits[i]]:
build(i+1, comb+c)
build(0, “”)
return output
- N-Queens
Solved
Hard
Topics
Companies
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
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 1:
Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[”..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [[“Q”]]
Constraints:
1 <= n <= 9
https://leetcode.com/problems/n-queens/description/
Trick to know if pos or neg diagonals are occupied
## neg Diag goes from top left to bottom right, in this case along the diag r-c is equal
## Pos diag goes from bottom left to top right in this case along the diag r+c is equal
## For each queen, place it at every colum in the given row to see if its valid position,
## if it is, then call backtrack to pass it on to the next queen and row (each queen will have it's own row)
from collections import defaultdict
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
b = [["." for i in range(n)] for j in range(n)]
occupied_row = set()
occupied_col = set()
occupied_lr = set() # r-c
occupied_rl = set() # r+c
movements = [[0,1], [1,0], [-1,0], [0, -1]]
res = []
def isValid(r,c):
if (r in occupied_row or c in occupied_col or r-c in occupied_lr or r+c in occupied_rl):
return False
return True
def dfs(row, queens, board):
if row == n:
res.append(["".join(row) for row in board])
return
for col in range(n):
if (row in range(n) and col in range(n) and isValid(row, col)):
occupied_row.add(row)
occupied_col.add(col)
occupied_lr.add(row-col)
occupied_rl.add(row+col)
board[row][col] = "Q"
dfs(row+1, queens, board[:])
occupied_row.remove(row)
occupied_col.remove(col)
occupied_lr.remove(row-col)
occupied_rl.remove(row+col)
board[row][col] = "."
return
dfs(0, 0, b[:])
return res
