LeetCode Hot 100 | 回溯（下）· 全排列与N皇后（C++ 题解）

LeetCode Hot 100 | 回溯下C 题解目录LeetCode Hot 100 | 回溯下C 题解前言1. 22. 括号生成 题目描述解题思路复杂度分析C 代码2. 79. 单词搜索 题目描述解题思路复杂度分析C 代码3. 131. 分割回文串 题目描述解题思路复杂度分析C 代码4. 51. N 皇后 题目描述解题思路复杂度分析C 代码总结前言回溯下篇继续深入涵盖括号生成、矩阵路径搜索、回文切割和 N 皇后四道经典题目。这些题目均以 DFS 剪枝为核心重点在于如何设计递归边界和状态还原。1. 22. 括号生成 题目描述数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3 输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1 输出[()]约束1 n 8解题思路用 DFS 枚举每一位填(还是)通过 left/right 计数器剪枝只要left n就可以加左括号只要right left就可以加右括号保证括号合法性left n right n时记录结果以n2为例推导过程步骤tmpleftright操作1“”00加(2“(”10加(3“((”20加)4“(()”21加)5“(())”22记录 ✓复杂度分析时间O(4^n / √n)卡特兰数空间O(n)递归栈深度C 代码classSolution{public:vectorstringgenerateParenthesis(intn){intleft0;intright0;vectorstringans;string tmp;dfs(n,left,right,ans,tmp);returnans;}voiddfs(intn,intleft,intright,vectorstringans,string tmp){if(leftnrightn){ans.push_back(tmp);return;}if(leftn){tmp.push_back(();dfs(n,left1,right,ans,tmp);tmp.pop_back();}if(rightleft){tmp.push_back());dfs(n,left,right1,ans,tmp);tmp.pop_back();}}};2. 79. 单词搜索 题目描述给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED 输出true示例 2输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEE 输出true约束m board.length,n board[i].length1 m, n 6,1 word.length 15解题思路从每个与word[0]匹配的位置出发 DFS用visit数组标记已访问四方向递归搜索。以word AB为例从(0,0)开始步骤位置indexboard[r][c]word[index]visit状态1(0,0)0‘A’‘A’标记已访问2(0,1)1‘B’‘B’标记已访问返回 true复杂度分析时间O(m × n × 4^L)L 为 word 长度空间O(m × n)visit 数组 递归栈C 代码classSolution{private:intmaxRow;intmaxClom;public:boolexist(vectorvectorcharboard,string word){maxRowboard.size();maxClomboard[0].size();intansfalse;intindex0;vectorvectorboolvisit(maxRow,vectorbool(maxClom,false));for(inti0;imaxRow;i){for(intj0;jmaxClom;j){if(board[i][j]word[0]){ansdfs(board,word,i,j,index,visit);if(ans)returntrue;}}}returnans;}booldfs(vectorvectorcharboard,string word,introw,intclom,intindex,vectorvectorboolvisit){if(indexword.size())returntrue;if(row0||rowmaxRow||clom0||clommaxClom||board[row][clom]!word[index]||visit[row][clom])returnfalse;visit[row][clom]true;boolansfalse;ans|dfs(board,word,row1,clom,index1,visit);ans|dfs(board,word,row-1,clom,index1,visit);ans|dfs(board,word,row,clom1,index1,visit);ans|dfs(board,word,row,clom-1,index1,visit);visit[row][clom]false;returnans;}};3. 131. 分割回文串 题目描述给你一个字符串s请你将s分割成一些子串使每个子串都是回文串。返回s所有可能的分割方案。示例 1输入s aab 输出[[a,a,b],[aa,b]]示例 2输入s a 输出[[a]]约束1 s.length 16s仅由小写英文字母组成解题思路从 index 开始枚举每个可能的子串结束位置 i若s[index..i]是回文则加入路径并递归之后回溯。以s aab为例步骤indexi子串是否回文tmp100“a”✓[“a”]211“a”✓[“a”,“a”]322“b”✓[“a”,“a”,“b”] ← 记录412“ab”✗跳过501“aa”✓[“aa”]622“b”✓[“aa”,“b”] ← 记录复杂度分析时间O(n × 2^n)空间O(n)递归栈C 代码classSolution{public:vectorvectorstringpartition(string s){vectorvectorstringans;vectorstringtmp;dfs(s,0,ans,tmp);returnans;}voiddfs(string s,intindex,vectorvectorstringans,vectorstringtmp){if(indexs.size()){ans.push_back(tmp);return;}for(intiindex;is.size();i){if(isHW(s,index,i)){tmp.push_back(s.substr(index,i-index1));dfs(s,i1,ans,tmp);tmp.pop_back();}}}boolisHW(string s,intleft,intright){while(leftright){if(s[left]!s[right--])returnfalse;}returntrue;}};4. 51. N 皇后 题目描述按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n × n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n 皇后问题的解决方案。示例 1输入n 4 输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]示例 2输入n 1 输出[[Q]]约束1 n 9解题思路逐行放置皇后用三个unordered_set分别记录已占用的列、正对角线行列相等和反对角线行-列相等以 O(1) 判断冲突。以n4第一行第 1 列0-indexed放皇后为例行尝试列clom_setadd_setsub_set合法01{1}{1}{-1}✓13{1,3}{1,4}{-1,-2}✓20{0,1,3}{1,2,4}{-1,-2,2}✓32{0,1,2,3}{1,2,4,5}{-1,-2,1,2}✓ → 记录复杂度分析时间O(n!)空间O(n)C 代码classSolution{public:vectorvectorstringsolveNQueens(intn){unordered_setintclom_set;unordered_setintadd_set;unordered_setintsub_set;vectorstringtmp(n,string(n,.));vectorvectorstringans;dfs(n,ans,clom_set,add_set,sub_set,0,tmp);returnans;}voiddfs(intn,vectorvectorstringans,unordered_setintclom_set,unordered_setintadd_set,unordered_setintsub_set,introw,vectorstringtmp){if(rown){ans.push_back(tmp);return;}for(inti0;in;i){if(clom_set.count(i)||add_set.count(rowi)||sub_set.count(row-i))continue;clom_set.insert(i);add_set.insert(rowi);sub_set.insert(row-i);tmp[row][i]Q;dfs(n,ans,clom_set,add_set,sub_set,row1,tmp);tmp[row][i].;clom_set.erase(i);add_set.erase(rowi);sub_set.erase(row-i);}}};总结题号题目难度核心技巧时间复杂度22括号生成中等DFS left/right 计数剪枝O(4^n/√n)79单词搜索中等DFS visit 标记 四方向搜索O(m×n×4^L)131分割回文串中等DFS 回文判断 回溯O(n×2^n)51N 皇后困难DFS 三集合剪枝O(n!)