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:

1. Path: choices already made;
2. Selection list: currently available selections;
3. 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