当前位置:网站首页>Leetcode backtracking method
Leetcode backtracking method
2022-07-05 06:13:00 【Dawnlighttt】
List of articles
q22 Bracket generation
Answer key
Let's solve this problem in a different way , The topic requires to use n Arrange brackets , We are from 2 * n Choose between the brackets to arrange them from left to right . At this time, we found out , We have chosen more left parentheses than right parentheses , such as "((("、"(()"、"(())“ Such a situation is allowed , however ”())" Such a situation cannot happen . So we made such a strategy at the beginning :
- As long as the left bracket always has , Then you can always choose the left bracket
- As long as the number of left parentheses is greater than the number of right parentheses , We can choose the right bracket
- When the number of parentheses equals 2 * n, Indicates that an arrangement has been obtained
func generateParenthesis(n int) []string {
res := []string{
}
var dfs func(lBracket int, rBracket int, path string)
dfs = func(lBracket int, rBracket int, path string){
if len(path) >= 2 * n {
res = append(res, path)
return
}
if lBracket > 0 {
dfs(lBracket - 1, rBracket, path + "(")
}
if rBracket > lBracket {
dfs(lBracket, rBracket - 1, path + ")")
}
}
dfs(n, n, "")
return res
}
q40 Combinatorial summation 2
Answer key
This problem uses dfs To solve , First, clarify the situation of reaching the leaf node , Is that when target Be reduced to 0 When , Then go through candidates The subscript , To create a new branch , And subscript as dfs Function parameters to pass parameters . At the same time, weight removal and pruning are needed , When the present candidates When the element of is the same as the previous element , Just skip this loop ; When the currently traversed element ratio target When I was young , Because the array has been ordered , So direct return that will do , Finally, continue recursion along this node .
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
var res [][]int
dfs(candidates, nil, target, 0, &res)
return res
}
func dfs(candidates []int, nums []int, target int, left int, res *[][]int) {
// Recursive export
if target == 0 {
tmp := make([]int, len(nums))
copy(tmp, nums)
*res = append(*res, tmp)
return
}
for i := left; i < len(candidates); i++ {
if i != left && candidates[i] == candidates[i - 1] {
// duplicate removal
continue
}
if target < candidates[i] {
// prune
return
}
// Direct transmission append(nums, candidates[i]) In fact, it includes the backtracking operation ,nums The array has not been changed
dfs(candidates, append(nums, candidates[i]), target - candidates[i], i + 1, res)
}
}
q46 Full Permutation
Answer key
This problem uses dfs To solve , The condition for judging leaf nodes is cur The length of the array and nums The length is the same , At this time cur Array add res Array . Then traverse nums Array to select numbers , To create a new branch , Inside a loop, you need to traverse cur Array , See if the selected number repeats , No problem, just continue along this branch .
func permute(nums []int) [][]int {
var res [][]int
dfs(nums, []int{
}, &res)
return res
}
func dfs(nums []int, cur []int, res *[][]int) {
if len(nums) == len(cur) {
tmp := make([]int, len(cur))
copy(tmp, cur)
*res = append(*res, tmp)
return
}
for i := 0; i < len(nums); i++ {
exist := false
for j := 0; j < len(cur); j++ {
if nums[i] == cur[j] {
exist = true
break
}
}
if exist == true {
continue
}
dfs(nums, append(cur, nums[i]), res)
}
}
边栏推荐
- Smart construction site "hydropower energy consumption online monitoring system"
- Daily question 1189 Maximum number of "balloons"
- Leetcode-556: the next larger element III
- LaMDA 不可能觉醒吗?
- API related to TCP connection
- JS quickly converts JSON data into URL parameters
- LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively
- Leetcode recursion
- The connection and solution between the shortest Hamilton path and the traveling salesman problem
- leetcode-6108:解密消息
猜你喜欢
Dynamic planning solution ideas and summary (30000 words)
1.15 - input and output system
1.14 - 流水线
Arduino 控制的 RGB LED 无限镜
SPI 详解
Introduction and experience of wazuh open source host security solution
LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively
LeetCode 0107. Sequence traversal of binary tree II - another method
6. Logistic model
Groupbykey() and reducebykey() and combinebykey() in spark
随机推荐
Some common problems in the assessment of network engineers: WLAN, BGP, switch
1996. number of weak characters in the game
[rust notes] 16 input and output (Part 1)
Leetcode-6108: decrypt messages
Appium automation test foundation - Summary of appium test environment construction
Leetcode recursion
MIT-6874-Deep Learning in the Life Sciences Week 7
liunx启动redis
Dichotomy, discretization, etc
Groupbykey() and reducebykey() and combinebykey() in spark
Appium自动化测试基础 — Appium测试环境搭建总结
LeetCode 0107.二叉树的层序遍历II - 另一种方法
leetcode-31:下一个排列
Full Permutation Code (recursive writing)
[practical skills] how to do a good job in technical training?
Leetcode-1200: minimum absolute difference
Dynamic planning solution ideas and summary (30000 words)
Leetcode-3: Longest substring without repeated characters
A reason that is easy to be ignored when the printer is offline
Leetcode heap correlation