# 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:

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:
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:
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()
```

Tags: leetcode

Posted by BizLab on Mon, 23 May 2022 11:25:19 +0300