Aug 12, 2024 | monday 2:00 pm
This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
MediumBacktracking
Try it yourself here!
Problem Statement: Find all the possible combinations of subsets for nums.
Example:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
The key insight for this problem comes from observing the pattern in the example. For each element at index i, we have two choices:
Backtracking Algorithm:
Complexity:
Time: O(n * 2^n), where n is the length of nums. For each number, we either choose to include or exclude the next number, thus resulting in a 2^n extra time complexity.
Space: O(n), where n is the size of nums and the worst case the size of the recursive stack is n.
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
def backtrack(i):
if i >= len(nums):
res.append(subset[:])
return
# Include element
subset.append(nums[i])
dfs(i + 1)
# Don't include element
subset.pop()
dfs(i + 1)
dfs(0)
return res
MediumBacktracking
Try it yourself here!
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def backtrack(remain, comb, start):
if remain == 0:
res.append(comb[:])
if remain < 0:
return
for i in range(start, len(candidates)):
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
backtrack(target, [], 0)
return res
MediumBacktracking
Try it yourself here!
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
seen = set()
def backtrack(curr):
if len(curr) == len(nums):
res.append(curr[:])
for n in nums:
if n not in seen:
seen.add(n)
curr.append(n)
backtrack(curr)
curr.pop()
seen.remove(n)
backtrack([])
return res
Complexity:
MediumBacktracking
Try it yourself here!
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
def backtrack(i):
if i == len(nums):
res.append(curr[:])
return
curr.append(nums[i])
backtrack(i + 1)
curr.pop()
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1)
curr = []
backtrack(0)
return res
Complexity:
MediumBacktracking
Try it yourself here!
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
def backtrack(remain, comb, start):
if remain == 0:
res.append(comb[:])
if remain <= 0:
return
prev = float("-inf")
for i in range(start, len(candidates)):
if candidates[i] == prev:
continue
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i + 1)
comb.pop()
prev = candidates[i]
backtrack(target, [], 0)
return res
MediumBacktracking
Try it yourself here!
def exist(self, board: List[List[str]], word: str) -> bool:
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
def backtrack(i, j, wordLeft):
if len(wordLeft) == 0:
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != wordLeft[0]:
return False
board[i][j] = "#"
for x, y in directions:
new_i, new_j = i + x, j + y
if backtrack(new_i, new_j, wordLeft[1:]):
return True
board[i][j] = wordLeft[0]
return False
for m in range(len(board)):
for n in range(len(board[0])):
if backtrack(m, n, word):
return True
return False
Complexity:
Time: O(n * 3^L), where n is the number of cells on the board. L is the length of the word, and at any point in the board other than the first call, there is 3 possible directions to go.
Space: O(L), The recursion stack will ever be at most size L.
MediumBacktracking
Try it yourself here!
def partition(self, s: str) -> List[List[str]]:
def isPalindrome(s, left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def backtrack(i):
if i == len(s):
res.append(part[:])
return
for j in range(i, len(s)):
if isPalindrome(s, i, j):
part.append(s[i:j+1])
backtrack(j + 1)
part.pop()
res = []
part = []
backtrack(0)
return res
Complexity:
MediumBacktracking
Try it yourself here!
def letterCombinations(self, digits: str) -> List[str]:
mp = { 2: "abc", 3: "def", 4: "ghi", 5:"jkl", 6:"mno", 7:"pqrs", 8:"tuv", 9: "wxyz"}
if not digits:
return []
res = []
def backtrack(i, strSoFar):
if i == len(digits):
res.append(strSoFar)
return
combStr = mp[int(digits[i])]
for c in combStr:
strSoFar += c
backtrack(i + 1, strSoFar)
strSoFar = strSoFar[:-1]
backtrack(0, "")
return res
Complexity: