• 代码随想录笔记--回溯算法篇

    目录

    1--回溯算法理论基础

    2--组合问题

    3--组合问题的剪枝操作

    4--组合总和III

    5--电话号码的字母组合

    6--组合总和

    7--组合总和II

    8--分割回文串

    9--复原 IP 地址

    10--子集

    11--子集II

    12--递增子序列

    13--全排列

    14--全排列II

    15--N皇后

    16--解数独

    1--回溯算法理论基础

            回溯算法本质上是一个暴力搜索的过程，其常用于解决组合、切割、子集、排列等问题，其一般模板如下：

    1. void backTracking(参数){
    2.     if(终止条件){
    3.     // 1. 收获结果;
    4.     // 2. return;
    5.     }
    6.  
    7.     for(..遍历){
    8.         // 1. 处理节点
    9.         // 2. 递归搜索
    10.         // 3. 回溯 // 即撤销对节点的处理
    11.     }
    12.     return;
    13. }

    2--组合问题

    主要思路：

            基于回溯法，暴力枚举 k 个数，需注意回溯弹出元素的操作；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vectorint>> combine(int n, int k) {
    7.         std::vector<int> path;
    8.         backTracking(n, k, path, 1); // 从第 1 个数开始
    9.         return res;
    10.     }
    11.  
    12.     void backTracking(int n, int k, std::vector<int> path, int start){
    13.         if(path.size() == k){
    14.             res.push_back(path);
    15.             return;
    16.         }
    17.  
    18.         for(int i = start; i <= n; i++){
    19.             path.push_back(i);
    20.             backTracking(n, k, path, i + 1); // 递归暴力搜索下一个数
    21.             path.pop_back(); // 回溯
    22.         }
    23.     }
    24.  
    25. private:
    26.     std::vectorint>> res;
    27. };
    28.  
    29. int main(int argc, char* argv[]){
    30.     int n = 4, k = 2;
    31.     Solution S1;
    32.     std::vectorint>> res = S1.combine(n, k);
    33.     for(auto v : res){
    34.         for(int item : v) std::cout << item << " ";
    35.         std::cout << std::endl;
    36.     }
    37.     return 0;
    38. }

    3--组合问题的剪枝操作

            上题的组合问题中，对于进入循环体 for(int i = start; i <= n; i++)：

    已选择的元素数量为：path.size()

    仍然所需的元素数量为：k - path.size()

    剩余的元素集合为：n - i + 1

    则为了满足要求，必须满足：k-path.size() <= n - i + 1，即 i <= n - k + path.size() + 1

    因此，可以通过以下条件完成剪枝操作：

    for(int i = start; i <= i <= n - k + path.size() + 1; i++)

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vectorint>> combine(int n, int k) {
    7.         std::vector<int> path;
    8.         backTracking(n, k, path, 1); // 从第 1 个数开始
    9.         return res;
    10.     }
    11.  
    12.     void backTracking(int n, int k, std::vector<int> path, int start){
    13.         if(path.size() == k){
    14.             res.push_back(path);
    15.             return;
    16.         }
    17.  
    18.         for(int i = start; i <= n - k + path.size() + 1; i++){
    19.             path.push_back(i);
    20.             backTracking(n, k, path, i + 1); // 暴力下一个数
    21.             path.pop_back(); // 回溯
    22.         }
    23.     }
    24.  
    25. private:
    26.     std::vectorint>> res;
    27. };
    28.  
    29. int main(int argc, char* argv[]){
    30.     int n = 4, k = 2;
    31.     Solution S1;
    32.     std::vectorint>> res = S1.combine(n, k);
    33.     for(auto v : res){
    34.         for(int item : v) std::cout << item << " ";
    35.         std::cout << std::endl;
    36.     }
    37.     return 0;
    38. }

    4--组合总和III

    主要思路：

            类似于上面的组合问题，基于回溯来暴力枚举每一个数，需要注意剪枝操作；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vectorint>> combinationSum3(int k, int n) {
    7.         std::vector<int> path;
    8.         backTracking(k, n, 0, path, 1);
    9.         return res;
    10.     }
    11.  
    12.     void backTracking(int k, int n, int sum, std::vector<int>path, int start){
    13.         if(sum > n) return; // 剪枝
    14.         if(path.size() == k){ // 递归终止
    15.             if(sum == n){
    16.                 res.push_back(path);
    17.             }
    18.             return;
    19.         }
    20.  
    21.         for(int i = start; i <= 9 + path.size() - k + 1; i++){ // 剪枝
    22.             path.push_back(i);
    23.             sum += i;
    24.             backTracking(k, n, sum, path, i + 1); // 递归枚举下一个数
    25.             // 回溯
    26.             sum -= i;
    27.             path.pop_back();
    28.         }
    29.  
    30.     }
    31. private:
    32.     std::vectorint>> res;
    33. };
    34.  
    35. int main(int argc, char* argv[]){
    36.     int k = 3, n = 7;
    37.     Solution S1;
    38.     std::vectorint>> res = S1.combinationSum3(k, n);
    39.     for(auto v : res){
    40.         for(int item : v) std::cout << item << " ";
    41.         std::cout << std::endl;
    42.     }
    43.     return 0;
    44. }

    5--电话号码的字母组合

    主要思路：

            根据传入的字符串，遍历每一个数字字符，基于回溯法，递归遍历每一个数字字符对应的字母；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector letterCombinations(std::string digits) {
    8.         if(digits.length() == 0) return res;
    9.         std::vector letter = {"", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    10.         backTracking(digits, letter, 0);
    11.         return res;
    12.     }
    13.  
    14.     void backTracking(std::string digits, std::vector letter, int cur){
    15.         if(cur == digits.size()){
    16.             res.push_back(tmp);
    17.             return;
    18.         }
    19.         int letter_idx = digits[cur] - '0';
    20.         int letter_size = letter[letter_idx].size();
    21.         for(int i = 0; i < letter_size; i++){
    22.             tmp.push_back(letter[letter_idx][i]);
    23.             backTracking(digits, letter, cur+1);
    24.             // 回溯
    25.             tmp.pop_back();
    26.         }
    27.     }
    28.  
    29. private:
    30.     std::vector res;
    31.     std::string tmp;
    32. };
    33.  
    34. int main(int argc, char* argv[]){
    35.     std::string test = "23";
    36.     Solution S1;
    37.     std::vector res = S1.letterCombinations(test);
    38.     for(std::string str : res) std::cout << str << " ";
    39.     std::cout << std::endl;
    40.     return 0;
    41. }

    6--组合总和

    主要思路：

            经典组合问题，通过回溯法暴力递归遍历；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vectorint>> combinationSum(std::vector<int>& candidates, int target) {
    7.         if(candidates.size() == 0) return res;
    8.         backTracking(candidates, target, 0, 0, path);
    9.         return res;
    10.     }
    11.  
    12.     void backTracking(std::vector<int>& candidates, int target, int sum, int start, std::vector<int>path){
    13.         if(sum > target) return; // 剪枝
    14.         if(sum == target) {
    15.             res.push_back(path);
    16.             return;
    17.         }
    18.  
    19.         for(int i = start; i < candidates.size(); i++){
    20.             sum += candidates[i];
    21.             path.push_back(candidates[i]);
    22.             backTracking(candidates, target, sum, i, path);
    23.             // 回溯
    24.             sum -= candidates[i];
    25.             path.pop_back();
    26.         }
    27.     }
    28.  
    29. private:
    30.     std::vectorint>> res;
    31.     std::vector<int> path;
    32. };
    33.  
    34. int main(int argc, char* argv[]){
    35.     // candidates = [2,3,6,7], target = 7
    36.     std::vector<int> test = {2, 3, 6, 7};
    37.     int target = 7;
    38.     Solution S1;
    39.     std::vectorint>> res = S1.combinationSum(test, target);
    40.  
    41.     for(auto vec : res){
    42.         for(int val : vec) std::cout << val << " ";
    43.         std::cout << std::endl; 
    44.     }
    45.  
    46.     return 0;
    47. }

    7--组合总和II

    主要思路：

            基于回溯法，暴力递归遍历数组；

            本题不能包含重复的组合，但由于有重复的数字，因此需要进行树层上的去重；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vectorint>> combinationSum2(std::vector<int>& candidates, int target) {
    8.         if(candidates.size() == 0) return res;
    9.         std::sort(candidates.begin(), candidates.end());
    10.         std::vector<bool> visited(candidates.size(), false);
    11.         backTracking(candidates, target, 0, 0, visited);
    12.         return res;
    13.     }
    14.  
    15.     void backTracking(std::vector<int>& candidates, int target, int sum, int start, std::vector<bool>& visited){
    16.         if(sum > target) return; // 剪枝
    17.         if(sum == target){
    18.             res.push_back(path);
    19.             return;
    20.         }
    21.         for(int i = start; i < candidates.size(); i++){
    22.             // 树层剪枝去重
    23.             if(i > 0 && candidates[i-1] == candidates[i]){
    24.                 if(visited[i-1] == false) continue;
    25.             }
    26.             sum += candidates[i];
    27.             path.push_back(candidates[i]);
    28.             visited[i] = true;
    29.             backTracking(candidates, target, sum, i+1, visited);
    30.             // 回溯
    31.             sum -= candidates[i];
    32.             path.pop_back();
    33.             visited[i] = false;
    34.         }
    35.     }
    36.  
    37. private:
    38.     std::vectorint>> res;
    39.     std::vector<int> path;
    40. };
    41.  
    42. int main(int argc, char* argv[]){
    43.     // candidates = [10,1,2,7,6,1,5], target = 8
    44.     std::vector<int> test = {10, 1, 2, 7, 6, 1, 5};
    45.     int target = 8;
    46.     Solution S1;
    47.     std::vectorint>> res = S1.combinationSum2(test, target);
    48.  
    49.     for(auto vec : res){
    50.         for(int val : vec) std::cout << val << " ";
    51.         std::cout << std::endl; 
    52.     }
    53.  
    54.     return 0;
    55. }

    8--分割回文串

    主要思路：

            基于回溯法，暴力加入子串，判断每一个子串是否是一个回文子串，如果不是回文子串则跳过，否则继续，直到将字符串的所有字符都遍历完；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector> partition(std::string s) {
    8.         if(s.length() == 0) return res;
    9.         backTracking(s, 0);
    10.         return res;
    11.     }
    12.  
    13.     void backTracking(std::string s, int startIdx){
    14.         if(startIdx >= s.size()){
    15.             res.push_back(tmp);
    16.             return;
    17.         }
    18.  
    19.         for(int i = startIdx; i < s.size(); i++){
    20.             std::string str = s.substr(startIdx, i - startIdx + 1);
    21.             if(is_valid(str) == false) continue; // 不合法的
    22.             // 合法的
    23.             tmp.push_back(str);
    24.             backTracking(s, i+1);
    25.             // 回溯
    26.             tmp.pop_back();
    27.         }
    28.     }
    29.  
    30.     // 判断是否是回文子串
    31.     bool is_valid(std::string str){
    32.         for(int i = 0, j = str.size()-1; i <= j; i++, j--){
    33.             if(str[i] != str[j]) return false;
    34.         }
    35.         return true;
    36.     }
    37.  
    38. private:
    39.     std::vector> res;
    40.     std::vector tmp;
    41. };
    42.  
    43. int main(int argc, char* argv[]){
    44.     // s = "aab"
    45.     std::string str = "aab";
    46.     Solution S1;
    47.     std::vector> res = S1.partition(str);
    48.     for(auto vec : res){
    49.         for(std::string s : vec) std::cout << s << " ";
    50.         std::cout << std::endl;
    51.     }
    52.     return 0;
    53. }

    9--复原 IP 地址

    主要思路：

            基于回溯法，递归遍历数字字符串，需要判断数字字符串是否合法；

            递归终止条件是当前加入的 ‘.’ 号已经为 3 个了，这时还需要判断最后一个数字字符串是否合法；

            比较难的地方可能在于判断字符是否有效；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector restoreIpAddresses(std::string s) {
    8.         if(s.length() < 4 || s.length() > 12) return res; // 剪枝
    9.         backTracking(s, 0, 0);
    10.         return res;
    11.     }
    12.  
    13.     void backTracking(std::string s, int start_inx, int numpoints){
    14.         if(numpoints == 3){
    15.             std::string str = s.substr(start_inx, s.length() - start_inx);
    16.             if(isvalid(str)){
    17.                 res.push_back(s);
    18.                 return;
    19.             }
    20.         }
    21.  
    22.         for(int i = start_inx; i < s.length(); i++){
    23.             std::string str = s.substr(start_inx, i - start_inx + 1);
    24.             if(isvalid(str) == false) break;
    25.             s.insert(s.begin() + i + 1, '.'); // 插入 '.'
    26.             numpoints += 1;
    27.             backTracking(s, i + 2, numpoints); // 从 i + 2 开始，因为新加入了一个 '.'字符
    28.             // 回溯
    29.             s.erase(s.begin() + i + 1);
    30.             numpoints -= 1;
    31.         }
    32.     }
    33.  
    34.     bool isvalid(std::string str){
    35.         int len = str.length();
    36.         if(len <= 0 || len > 3) return false;
    37.         if (str[0] == '0' && len > 1) { // 不合法
    38.             return false;
    39.         }
    40.         int num = 0;
    41.         for(int i = 0; i < len; i++){
    42.             num = num * 10 + (str[i] - '0');
    43.             if(num > 255) return false;
    44.         }
    45.         return true;
    46.     }
    47.  
    48. private:
    49.     std::vector res;
    50.     int numpoints = 0;
    51. };
    52.  
    53. int main(int argc, char* argv[]){
    54.     // s = "25525511135"
    55.     std::string test = "25525511135";
    56.     Solution S1;
    57.     std::vector res = S1.restoreIpAddresses(test);
    58.     for(auto str : res) std::cout << str << " ";
    59.     std::cout << std::endl;
    60.     return 0;
    61. }

    10--子集

    主要思路：

            基于回溯法，暴力遍历加入每一个元素，每加入一个元素就收获一次结果；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vectorint>> subsets(std::vector<int>& nums) {
    7.         dfs(nums, 0);
    8.         return res;
    9.     }
    10.  
    11.     void dfs(std::vector<int>& nums, int start_idx){
    12.         if(start_idx > nums.size()) return; // 可以删去
    13.         res.push_back(path);
    14.         for(int i = start_idx; i < nums.size(); i++){
    15.             path.push_back(nums[i]);
    16.             dfs(nums, i+1);
    17.             // 回溯
    18.             path.pop_back();
    19.         }
    20.     }
    21.  
    22. private:
    23.     std::vectorint>> res;
    24.     std::vector<int> path;
    25. };
    26.  
    27.  
    28. int main(int argc, char* argv[]){
    29.     // nums = [1,2,3]
    30.     std::vector<int> nums = {1, 2, 3};
    31.     Solution S1;
    32.     std::vectorint>> res = S1.subsets(nums);
    33.     for(auto vec : res){
    34.         for(auto val : vec) std::cout << val << " ";
    35.         std::cout << std::endl;
    36.     }
    37.     return 0;
    38. }

    11--子集II

    主要思路：
            类似于上题的子集问题，暴力遍历每一个元素，每加入一个元素收获一次结果；

            需要注意的是，本题需要去重，因此采用类似组合问题的去重逻辑：先对数组进行排序，再进行树层上的去重；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vectorint>> subsetsWithDup(std::vector<int>& nums) {
    8.         std::sort(nums.begin(), nums.end());
    9.         std::vector<bool> visited(nums.size(), false);
    10.         dfs(nums, 0, visited);
    11.         return res;
    12.     }
    13.  
    14.     void dfs(std::vector<int>& nums, int start_idx, std::vector<bool>& visited){
    15.         if(start_idx > nums.size()) return; // 可以省略
    16.         res.push_back(path);
    17.         for(int i = start_idx; i < nums.size(); i++){
    18.             // 树层上去重
    19.             if(i > 0 && nums[i-1] == nums[i] && visited[i-1] == false){
    20.                 continue;
    21.             }
    22.             path.push_back(nums[i]);
    23.             visited[i] = true;
    24.             dfs(nums, i+1, visited);
    25.             // 回溯
    26.             path.pop_back();
    27.             visited[i] = false;
    28.         }
    29.     }
    30.  
    31. private:
    32.     std::vectorint>> res;
    33.     std::vector<int> path;
    34. };
    35.  
    36.  
    37. int main(int argc, char* argv[]){
    38.     // nums = [1,2,2]
    39.     std::vector<int> nums = {1, 2, 2};
    40.     Solution S1;
    41.     std::vectorint>> res = S1.subsetsWithDup(nums);
    42.     for(auto vec : res){
    43.         for(auto val : vec) std::cout << val << " ";
    44.         std::cout << std::endl;
    45.     }
    46.     return 0;
    47. }

    12--递增子序列

    主要思路：

            基于回溯法，暴力遍历每一个元素；

            判断一个元素是否可以加入路径的条件：元素大于路径的最后一个结点（保证递增）；因为有重复的元素，因此需要在树层上进行去重，树层去重需要判断当前元素是否在遍历之前出现过，如果出现过则舍弃；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vectorint>> findSubsequences(std::vector<int>& nums) {
    8.         if(nums.size() == 0) return res;
    9.         backTracking(nums, 0);
    10.         return res;
    11.     }
    12.  
    13.     void backTracking(std::vector<int>& nums, int start_idx){
    14.         if(path.size() > 1){
    15.             res.push_back(path); // 每一层递归加入一个结果
    16.         }
    17.  
    18.         std::set<int> my_set; // 每一层递归新建一个set
    19.         for(int i = start_idx; i < nums.size(); i++){
    20.             if(path.size() > 0 && nums[i] < path.back() || my_set.find(nums[i]) != my_set.end()){ // 树层上去重
    21.                 continue;
    22.             }
    23.             path.push_back(nums[i]);
    24.             my_set.insert(nums[i]);
    25.             backTracking(nums, i+1);
    26.             // 回溯
    27.             path.pop_back();
    28.         }
    29.     }
    30.  
    31. private:
    32.     std::vectorint>> res;
    33.     std::vector<int> path;
    34. };
    35.  
    36. int main(int argc, char* argv[]){
    37.     // nums = [4,6,7,7]
    38.     std::vector<int> nums = {4, 6, 7, 7};
    39.     Solution S1;
    40.     std::vectorint>> res = S1.findSubsequences(nums);
    41.     for(auto vec : res){
    42.         for(int val : vec) std::cout << val << " ";
    43.         std::cout << std::endl;
    44.     }
    45.     return 0;
    46. }

    13--全排列

    主要思路：

            基于回溯法，暴力遍历每一个元素；由于是排列，因此结果的元素数量肯定与数组大小相同；

            每一轮递归，都需要从索引 0 开始遍历；使用一个数组来记录当前元素是否被访问过；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vectorint>> permute(std::vector<int>& nums) {
    7.         if(nums.size() == 0) return res;
    8.         std::vector<bool> visited(nums.size(), false);
    9.         backTracking(nums, visited);
    10.         return res;
    11.     }
    12.  
    13.     void backTracking(std::vector<int>& nums, std::vector<bool>& visited){
    14.         if(path.size() == nums.size()){
    15.             res.push_back(path);
    16.             return;
    17.         }
    18.         for(int i = 0; i < nums.size(); i++){
    19.             if(visited[i] == true) continue;
    20.             path.push_back(nums[i]);
    21.             visited[i] = true;
    22.             backTracking(nums, visited);
    23.             // 回溯
    24.             visited[i] = false;
    25.             path.pop_back();
    26.         }
    27.     }
    28. private:
    29.     std::vectorint>> res;
    30.     std::vector<int> path;
    31. };
    32.  
    33. int main(int argc, char* argv[]){
    34.     // nums = [1,2,3]
    35.     std::vector<int> nums = {1, 2, 3};
    36.     Solution S1;
    37.     std::vectorint>> res = S1.permute(nums);
    38.     for(auto vec : res){
    39.         for(auto val : vec) std::cout << val << " ";
    40.         std::cout << std::endl;
    41.     }
    42.     return 0;
    43. }

    14--全排列II

    主要思路：

            主要思路类似于上题的全排列，但本题的数组含有重复元素，因此需要进行树层上的去重（先对数组进行排序）；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vectorint>> permuteUnique(std::vector<int>& nums) {
    8.         if(nums.size() == 0) return res;
    9.         std::sort(nums.begin(), nums.end());
    10.         std::vector<bool> visited(nums.size(), false);
    11.         backTracking(nums, visited);
    12.         return res;
    13.     }
    14.  
    15.     void backTracking(std::vector<int>& nums, std::vector<bool>& visited){
    16.         if(path.size() == nums.size()){
    17.             res.push_back(path);
    18.             return;
    19.         }
    20.         for(int i = 0; i < nums.size(); i++){
    21.             if(i > 0 && nums[i-1] == nums[i] && visited[i-1] == false) continue; // 树层上去重
    22.             if(visited[i] == true) continue; // 重复元素
    23.             
    24.             path.push_back(nums[i]);
    25.             visited[i] = true;
    26.             backTracking(nums, visited);
    27.             // 回溯
    28.             path.pop_back();
    29.             visited[i] = false;
    30.         }
    31.     }
    32.  
    33. private:
    34.     std::vectorint>> res;
    35.     std::vector<int> path;
    36. };
    37.  
    38. int main(int argc, char* argv[]){
    39.     // nums = [1,1,2]
    40.     std::vector<int> nums = {1, 1, 2};
    41.     Solution S1;
    42.     std::vectorint>> res = S1.permuteUnique(nums);
    43.     for(auto vec : res){
    44.         for(auto val : vec) std::cout << val << " ";
    45.         std::cout << std::endl;
    46.     }
    47.     return 0;
    48. }

    15--N皇后

    主要思路：

            基于回溯法，递归每一行，暴力枚举每一列是否适合放皇后；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector> solveNQueens(int n) {
    8.         std::vector board(n, std::string(n, '.'));
    9.         backTracking(n, 0, board);
    10.         return res;
    11.     }
    12.  
    13.     void backTracking(int n, int row, std::vector& board){
    14.         if(row == n){
    15.             res.push_back(board);
    16.             return;
    17.         }
    18.         for(int col = 0; col < n; col++){
    19.             if(isValid(board, row, col)){ // [row, col]可以放一个皇后
    20.                 board[row][col] = 'Q';
    21.                 backTracking(n, row+1, board);
    22.                 // 回溯
    23.                 board[row][col] = '.';
    24.             }
    25.         }
    26.     }
    27.  
    28.     bool isValid(const std::vector& board, int row, int col){
    29.         // 检查行
    30.         for(int i = 0; i < row; i++){
    31.             if(board[i][col] == 'Q') return false;
    32.         }
    33.         // 检查列
    34.         for(int i = 0; i < board.size(); i++){
    35.             if(board[row][i] == 'Q') return false; 
    36.         }
    37.         // 检查主对角线
    38.         for(int i = row - 1, j = col - 1; i >=0 && j >=0; i--, j--){
    39.             if(board[i][j] == 'Q') return false;
    40.         }
    41.         // 检查反对角线
    42.         for(int i = row - 1, j = col + 1; i >= 0 && j <= board.size(); i--, j++){
    43.             if(board[i][j] == 'Q') return false;
    44.         }
    45.         return true;
    46.     }
    47.  
    48. private:
    49.     std::vector> res;
    50. };
    51.  
    52. int main(int argc, char* argv[]){
    53.     // n = 4
    54.     int n = 4;
    55.     Solution S1;
    56.     std::vector> res = S1.solveNQueens(n);
    57.     for(auto vec : res){
    58.         for(auto val : vec) std::cout << val << " ";
    59.         std::cout << std::endl;
    60.     }
    61.     return 0;
    62. }

    16--解数独

    主要思路：

            基于回溯法，两层循环分别判断行和列，枚举 9 个数是否适合加入到当前行和列；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     void solveSudoku(std::vectorchar>>& board) {
    8.         backTracking(board);
    9.     }
    10.  
    11.     bool backTracking(std::vectorchar>>& board){
    12.         for(int row = 0; row < board.size(); row++){
    13.             for(int col = 0; col < board[0].size(); col++){
    14.                 if(board[row][col] == '.'){
    15.                     for(char k = '1'; k <= '9'; k++){
    16.                         if(isValid(board, row, col, k)){
    17.                             board[row][col] = k;
    18.                             if(backTracking(board) == true){ // 递归
    19.                                 return true;
    20.                             }
    21.                             // 回溯
    22.                             board[row][col] = '.';
    23.                         }
    24.                     }
    25.                     return false; // 尝试了 9 个数也不能递归返回 true, 就返回 false
    26.                 }
    27.             }
    28.         }
    29.         return true; // 遍历完没有返回 false，说明找到的合适棋盘
    30.     }
    31.  
    32.     bool isValid(const std::vectorchar>>& board, int row, int col, char val){
    33.         // 检查同一行
    34.         for(int i = 0; i < board[0].size(); i++){
    35.             if(board[row][i] == val) return false;
    36.         }
    37.  
    38.         // 检查同一列
    39.         for(int i = 0; i < board.size(); i++){
    40.             if(board[i][col] == val) return false;
    41.         }
    42.  
    43.         // 检查九宫格
    44.         int startRow = (row / 3) * 3;
    45.         int startCol = (col / 3) * 3;
    46.         for (int i = startRow; i < startRow + 3; i++){ // 判断九宫格内是否重复
    47.             for (int j = startCol; j < startCol + 3; j++){
    48.                 if (board[i][j] == val){
    49.                     return false;
    50.                 }
    51.             }
    52.         }
    53.         return true;
    54.     }
    55. };
    56.  
    57. int main(int argc, char* argv[]){
    58.     std::vectorchar>> board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
    59.                                             {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
    60.                                             {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
    61.                                             {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
    62.                                             {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
    63.                                             {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
    64.                                             {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
    65.                                             {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
    66.                                             {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
    67.     Solution S1;
    68.     S1.solveSudoku(board);
    69.     for(auto vec : board){
    70.         for(auto val : vec) std::cout << val << " ";
    71.         std::cout << std::endl;
    72.     }                                        
    73.     return 0;
    74. }

  • 相关阅读:
    Promise简（resolve，reject，catch）
    Charles抓包工具的基本操作
    Aspose.Cells for Python via .NET crack
    JS/CSS 交互
    【frida实战】“一行”代码教你获取WeGame平台中所有的lua脚本
    竹间智能用认知智能为企业的发展提供助力
    如何借助边缘智能网关打造智慧城市便民驿站
    Win11系统电脑怎么C盘扩容教学
    MySQL - 如何判断一行扫描数？
    java18-枚举类和注解
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/132722009