LeetCode Day 27 (Day 26 is rest day) Backtracking Algorithm (3/6)
Published:
Started the third day of practice, after I positive, the fever, sore throat all experienced, but the studies still continue!
Question 1
Given an array of distinct integers
candidatesand a target integertarget, return a list of all unique combinations ofcandidateswhere the chosen numbers sum totarget. You may return the combinations in any order.The same number may be chosen from
candidatesan unlimited number of times. Two combinations are unique if thefrequency
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
targetis less than150combinations for the given input.
The number in candidates can be picked an unlimited number of times, as long as it comes up to traget. It’s still solved by recursion.
class Solution:
def backtracking(self, candidates, target, total, startIndex, path, result):
if total > target:
return
if total == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i, path, result)
total -= candidates[i]
path.pop()
def combinationSum(self, candidates, target):
result = []
self.backtracking(candidates, target, 0, 0, [], result)
return result
Question 2
Given a collection of candidate numbers (
candidates) and a target number (target), find all unique combinations incandidateswhere the candidate numbers sum totarget.Each number in
candidatesmay only be used once in the combination.Note: The solution set must not contain duplicate combinations.
This question is more restrictive than the previous one: it can only be used once in the candidates, but this time there are duplicate numbers in the candidates
class Solution:
def backtracking(self, candidates, target, total, startIndex, path, result):
if total == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
if i > startIndex and candidates[i] == candidates[i - 1]:
continue
if total + candidates[i] > target:
break
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i + 1, path, result)
total -= candidates[i]
path.pop()
def combinationSum2(self, candidates, target):
result = []
candidates.sort()
self.backtracking(candidates, target, 0, 0, [], result)
return result
Question 3
Given a string
s, partitionssuch that every substring of the partition is a palindrome. Return all possible palindrome partitioning ofs.
This question is a bit complicated, you need to consider different ways of splitting, as well as determining whether it is a palindrome or not. I couldn’t figure out how to write it using a for loop, so I had to look at other people’s solutions:
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
self.backtracking(s, 0, [], result)
return result
def backtracking(self, s, start_index, path, result ):
# Base Case
if start_index == len(s):
result.append(path[:])
return
for i in range(start_index, len(s)):
if self.is_palindrome(s, start_index, i):
path.append(s[start_index:i+1])
self.backtracking(s, i+1, path, result)
path.pop()
def is_palindrome(self, s: str, start: int, end: int) -> bool:
i: int = start
j: int = end
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True