Backtracking algorithm framework
Backtracking is closely related to DFS.
Backtracking means "withdraw one step"
Solving a backtracking problem is actually a traversal process of decision tree. Just think about three questions:
- Path: choices already made;
- Selection list: currently available selections;
- End condition: a condition that reaches the bottom of the decision tree and cannot be selected.
res = [] def backtrack(Path, selection list): if Meet the end conditions: result.add(route) return for choice in Selection list: Make a choice backtrack(Path, selection list) Undo selection
Core: make a selection before recursive call and revoke the selection after call
Classical problem
Permutation
Traversing to the bottom of the tree, the path is a full arrangement. Traversal framework of multi fork tree:
def traverse(root): for(root.child): #Operations required for preorder traversal traverse(child) #Operations required for post order traversal
46. Full arrangement
Given a sequence without repeated numbers, all possible permutations are returned.
Define k: make decisions on elements with subscript k
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: if not nums: return [] res = [] self.backtrack(res,0,nums) return res def backtrack(self,res,k,nums): if k==len(nums): res.append(nums[:]) return for i in range(k,len(nums)): nums[i],nums[k] = nums[k],nums[i]#Select nums[i] self.backtrack(res,k+1,nums)#k+1, add num [i] to the path nums[i],nums[k] = nums[k],nums[i]#Undo selection
Subsets subsets
78. Subset
Given a set of integer arrays nums without duplicate elements, all possible subsets (power sets) of the array are returned.
Note: the solution set cannot contain duplicate subsets.
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: if not nums: return [] curr = [] res = [] self.backtrack(curr,res,0,nums) return res def backtrack(self,curr,res,k,nums): if k==len(nums): res.append(curr[:]) return #Uncheck num [k] self.backtrack(curr,res,k+1,nums) #Select nums[k] curr.append(nums[k]) self.backtrack(curr,res,k+1,nums) curr.pop()
Combination combination
77. Portfolio
Given two integers n and k, returns the combination of all possible k numbers in 1... N.
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: curr = [] res = [] self.backtrack(curr,res,1,k,n) return res def backtrack(self,curr,res,i,k,n): if len(curr)==k: res.append(curr[:]) return if i>(n-(k-len(curr)))+1:#prune return self.backtrack(curr,res,i+1,k,n) curr.append(i) self.backtrack(curr,res,i+1,k,n) curr.pop()
Pruning: take n=4, k=2 as an example
When curr = [], there must be at least two elements to choose from, k-len(curr)
If I > 3, the combination of two numbers must not be generated, (n - (k-len (curr)) + 1
De duplication strategy
The arrangement of repeated elements
47. Full arrangement II
Given a sequence that can contain repeated numbers, returns all non repeated permutations.
Take [2,2,3] as an example. If there are multiple 2 candidates, only the first 2 can be selected, and the latter 2 cannot be selected this time.
set() auxiliary judgment
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: if not nums: return [] res = [] self.backtrack(nums,0,res) return res def backtrack(self,nums,k,res): if k==len(nums): res.append(nums[:]) return seen = set() for i in range(k,len(nums)): if nums[i] not in seen: seen.add(nums[i]) nums[i],nums[k] = nums[k],nums[i] self.backtrack(nums,k+1,res) nums[i],nums[k] = nums[k],nums[i]
Subset problem with duplicate elements
90. Subset II
Given an integer array nums that may contain duplicate elements, return all possible subsets (power sets) of the array.
Note: the solution set cannot contain duplicate subsets.
class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: if not nums: return [] **nums.sort()** res = [] curr = [] self.backtrack(nums,curr,0,res) return res def backtrack(self,nums,curr,k,res): if k==len(nums): res.append(curr[:]) return #If num [k] is not selected, the elements equal to num [k] are not selected i = k+1 while i<len(nums) and nums[i]==nums[k]: i+=1 self.backtrack(nums,curr,i,res) curr.append(nums[k]) self.backtrack(nums,curr,k+1,res) curr.pop()
reference material:
LeetCode example | 03 from binary tree traversal to backtracking algorithm
labuladong