力扣题记之回溯
|
149
|
0
|
算法

1277 字
|
26 分钟

More content：LeetCode hot100@回溯

回溯算法可解决的问题类型：

17. 电话号码的字母组合✅

定义全局变量，精简递归函数参数

class Solution {
private:
    vector<string> res;
    string path;
    int n;
    unordered_map<char, string> mp;
public:
    void backtracking(string digits, int depth) {
        if(path.size() == n) {
            res.push_back(path);
            return ;
        }

        for(const char &i : mp[digits[depth]]) {
            path += i;
            backtracking(digits, depth + 1);
            path.erase(path.size() - 1, 1);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(!digits.size()) return res;
        
        mp['2'] = "abc";
        mp['3'] = "def";
        mp['4'] = "ghi";
        mp['5'] = "jkl";
        mp['6'] = "mno";
        mp['7'] = "pqrs";
        mp['8'] = "tuv";
        mp['9'] = "wxyz";

        n = digits.size();
        backtracking(digits, 0);

        return res;
    }
};

39. 组合总和✅

target递减，由两个参数变为一个参数

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void backtracking(vector<int>& candidates, int sub_target, int startIndex) {
        if(sub_target < 0) return ; //和超出目标了，作废
        if(!sub_target) { //和正好等于目标值，记录
            res.push_back(path);
            return ;
        }

        for(int i = startIndex; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            backtracking(candidates, sub_target - candidates[i], i); //允许重复选取当前元素，但不能回到之前的元素
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0);

        return res;
    }
};

40. 组合总和 II❌

跟上题的区别是数组中的元素有可能重复，且数组中的每个数字在每个组合中最多出现一次

如何在搜索的过程中去掉重复组合？

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void backtracking(vector<int>& candidates, int sub_target, int startIndex) {
        if(sub_target < 0) return ; //和超出目标了，作废
        if(!sub_target) { //和正好等于目标值，记录
            res.push_back(path);
            return ;
        }

        for(int i = startIndex; i < candidates.size(); i++) {
            //对同一树层（注意不是树枝）使用过的元素跳过
            if(i > startIndex && candidates[i] == candidates[i - 1]) continue;
     
            path.push_back(candidates[i]);
            backtracking(candidates, sub_target - candidates[i], i + 1); //不允许重复选取当前元素
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        ranges::sort(candidates); //先排序
        backtracking(candidates, target, 0);
    
        return res;
    }
};

216. 组合总和 III✅

更简单了

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void backTracking(int startNum, int n, int k) {
        if(k < 0 || n < 0) return ;
        if(!k && !n) {
            res.push_back(path);
            return ;
        }
        
        for(int i = startNum; i <= 9; i++) {
            path.push_back(i);
            backTracking(i + 1, n - i, k - 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backTracking(1, n, k);

        return res;
    }
};

77. 组合✅

设置遍历初始值

剪枝优化

class Solution {
private:
    vector<vector<int>> res;
    vector<int> v;
public:
    void backtracking(int k, int n) {
        if(v.size() == k) { //k个数够了 记录结果
            res.push_back(v);
            return ;
        }

        int start = 1;
        if(v.size()) start = v[v.size() - 1] + 1;
        // for(int i = start; i <= n; i++) {
        for(int i = start; i <= n - k + v.size() + 1; i++) { //剪枝：元素数量不够了就没必要遍历了
            v.push_back(i);
            backtracking(k, n);
            v.pop_back(); //回溯
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(k, n);

        return res;
    }
};

93. 复原 IP 地址✅

遍历回溯切割 + 检测非法字段

class Solution {
private:
    vector<string> res;
    string path;
public:
    void backTracking(string s, int depth, int startIndex) {
        if(depth == 4) {
            if(s.size() == startIndex) res.push_back(path);
            return ;
        }
  
        for(int i = 1; i <= 3 && startIndex + i <= s.size(); i++) { //遍历要切的位数    
            if(!checkIP(s, startIndex, i)) continue;
            path.append(s, startIndex, i);
            if(depth != 3) path += ".";
            backTracking(s, depth + 1, startIndex + i);
            if(depth != 3) path.erase(path.size() - 1, 1);
            path.erase(path.size() - i, i);
        }
    }

    bool checkIP(string s, int beginIndex, int len) {
        if(len != 1 && s[beginIndex] == '0') return false; //检测前导0
        int ip = 0;
        for(int i = 0; i < len; i++) {
            ip += (s[beginIndex + i] - '0') * pow(10, len - i - 1);
        }
        // cout << ip << endl;
        if(ip > 255) return false; 
        return true;
    }

    vector<string> restoreIpAddresses(string s) {
        backTracking(s, 0, 0);
        // checkIP(s, 0, 3);
        return res;
    }
};

131. 分割回文串✅

与93. 复原 IP 地址思路一样 但更简单一些

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;
public:
    void backTracking(string s, int startIndex) {
        if(s.size() == startIndex) {
            res.push_back(path);
            return ;
        }
  
        for(int i = 1; startIndex + i <= s.size(); i++) { //遍历要切的位数    
            if(!checkPalindrome(s, startIndex, i)) continue;
            path.push_back(s.substr(startIndex, i));
            backTracking(s, startIndex + i);
            path.pop_back();
        }
    }

    bool checkPalindrome(string s, int beginIndex, int len) {
        int l = beginIndex;
        int r = beginIndex + len - 1;
        while(l <= r) {
            if(s[l++] != s[r--]) return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        // if(checkPalindrome(s, 0, 3)) cout << "yes";
        // else cout << "no";
        return res;
    }
};

78. 子集✅

控制一下长度即可

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;

public:
    void backTracking(vector<int>& nums, int startIndex, int len) {
        if(path.size() == len) {
            res.push_back(path);
            return ;
        }

        for(int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backTracking(nums, i + 1, len);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        res.push_back({});
        res.push_back(nums);

        for(int i = 1; i < nums.size(); i++) {
            backTracking(nums, 0, i);
        }

        return res;
    }
};

90. 子集 II✅

还是同一树层去重

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> flags;
public:
    void backTracking(vector<int>& nums, int startIndex, int len) {
        if(path.size() == len) {
            res.push_back(path);
            return ;
        }

        for(int i = startIndex; i < nums.size(); i++) {
            //flags[i - 1] == 1说明num[i - 1]被同一树枝用过了
            //当nums[i] == nums[i - 1]时，flags[i - 1] == 0说明num[i - 1]被同一树层用过了
            if(i > 0 && nums[i] == nums[i - 1] && flags[i - 1] == 0) continue;
            path.push_back(nums[i]);
            flags[i] = 1;
            backTracking(nums, i + 1, len);
            flags[i] = 0;
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.push_back({});
        res.push_back(nums);

        flags.resize(nums.size(), 0);
        ranges::sort(nums);
        for(int i = 1; i < nums.size(); i++) {
            backTracking(nums, 0, i);
        }

        return res;
    }
};

46. 全排列✅

用一个数组来记录nums下标的状态，即记录下标对应的元素是否被用过(比如flags[2] = 1代表nums[2]被使用过了)

ps：为什么不直接记录元素是否被用过？因为元素中有负数，下标都是非负数，所以用下标来记录下标，反正nums数组的下标和元素对应关系不会变

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> flags;
public:
    void backTracking(vector<int>& nums) {
        if(path.size() == nums.size()) {
            res.push_back(path);
            return ;
        }

        for(int i = 0; i < nums.size(); i++) {
            if(flags[i]) continue;
            path.push_back(nums[i]);
            flags[i] = 1;
            backTracking(nums);
            path.pop_back();
            flags[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        flags.resize(nums.size(), 0);
        backTracking(nums);
        
        return res;
    }
};

47. 全排列 II❌

依旧用一个数组来记录nums下标的状态，关键是如何去重

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> flags;
public:
    void backTracking(vector<int>& nums) {
        if(path.size() == nums.size()) {
            res.push_back(path);
            return ;
        }

        for(int i = 0; i < nums.size(); i++) {
            //flags[i - 1] == 1，说明同一树枝nums[i - 1]使用过
            //flags[i - 1] == 0，说明同一树层nums[i - 1]使用过，因为flags状态是在同一树枝共享的，而不是树层，且遍历是按顺序来的
            //如果同一树层nums[i - 1]使用过则直接跳过
            if(i > 0 && nums[i] == nums[i - 1] && !flags[i-1]) continue;
            if(!flags[i]) {
                path.push_back(nums[i]);
                flags[i] = 1;
                backTracking(nums);
                path.pop_back();
                flags[i] = 0;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        flags.resize(nums.size(), 0);
        ranges::sort(nums);  
        backTracking(nums);
        
        return res;
    }
};

37. 解数独❌

一开始想的是跟51. N 皇后思路一样，按行往下递归搜，对列以及每一个可能的数字都遍历，但是超时，得用二维递归

二维递归：遍历行和列，递归进去的是确定的这个小格子（之前递归进去的都是行，一行一行递归着往下搜），小格子内填哪个数字的可能性用遍历实现

因为本题只有唯一解，不用一直存储答案，所以递归函数返回值为bool，遇到直接结束帝递归

class Solution {
public:
    bool backTracking(vector<vector<char>>& board) {
        for(int row = 0; row < board.size(); row++) { //遍历行
            for(int col = 0; col < board[0].size(); col++) { //遍历列
                if(board[row][col] != '.') continue;
                for(char num = '1'; num <= '9'; num++) {//当前小格子放哪个数合适
                    if(checkValid(board, row, col, num)) {
                        board[row][col] = num;                
                        if (backTracking(board)) return true; //如果找到一组答案立刻返回,因为唯一解
                        board[row][col] = '.';             
                    }
                }
                return false; // 9个数试完了都不行，返回false
            }
        }
        return true; //遍历完没有返回false，说明找到答案了
    }

    bool checkValid(vector<vector<char>>& board, int row, int col, int num) {
        for(int i = 0; i < 9; i++) { //检查行
            if(board[row][i] == num) return false;
        }
        for(int i = 0; i < 9; i++) { //检查列
            if(board[i][col] == num) return false;
        }
        //先确定所属单元格的左上角元素坐标
        //这段和代码随想录的思路竟然一模一样 变量名都一样。。。
        int startRow = row / 3 * 3; 
        int startCol = col / 3 * 3;
        for(int i = 0; i < 3; i++) { //检查单元格
            for(int j = 0; j < 3; j++) { 
                if(board[i + startRow][j + startCol] == num) return false;
            }      
        }

        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backTracking(board);
    }
};

51. N 皇后❌

思路没问题，先按行搜出所有方案，再对列、撇、捺进行合法性检查，但没想出撇和捺的检查公式，缺点是搜出所有方案在筛选，效率低

在搜的过程中就检查合法性，非法的直接跳过

class Solution {
private:
    vector<vector<string>> res;
public:
    void backTracking(vector<string> &tep, int n, int row) {
        if(row == n) {
            res.push_back(tep); 
            return ;
        }

        for(int col = 0; col < n; col++) { //只遍历当前行的每列，遍历行递归实现
            if(checkValid(row, col, tep, n)) { 
                tep[row][col] = 'Q';
                backTracking(tep, n, row + 1); //row相当于深度
                tep[row][col] = '.'; //回溯,撤销Q
            }
        }
    }

    bool checkValid(int row, int col, vector<string> &tep, int n) {
        for(int i = 0; i < n; i++) { //检查列
            if(tep[i][col] == 'Q') return false;
        }
      
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { //检查捺
            if(tep[i][j] == 'Q') {
                return false;
            }
        }

        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { //检查撇
            if(tep[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> tep(n, string(n, '.')); //初始化棋盘，等效于下面数行
        // vector<string> tep;
        // for(int i = 0; i < n; i++) {
        //     string s;
        //     for(int j = 0; j < n; j++) {
        //         s += '.';
        //     }
        //     tep.push_back(s);
        // }
        backTracking(tep, n, 0);
        
        return res;
    }
};


不准投币喔 👆

leetcode力扣回溯
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

															
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
力扣题记之hard

							
							

							
力扣题记之动态规划

							
							

							
LeetCode hot100@贪心

							
							

							
卡码题记之图论

							
							

							
笔试题记：24年腾讯音乐春招

							
							

							
力扣题记之贪心

							
							

							
笔试题记：23年网易秋招

							
							

							
LeetCode hot100@图论

							
							

							
LeetCode hot100@技巧

							
							

							
笔试题记：24年小米春招