回溯-子集_组合_排序_练习

本文主要是介绍回溯-子集_组合_排序_练习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

子集：

90. 子集 II

组合

leetcode17(中等): 电话号码的字母组合

leetcode39 组合总和:

去重复：

leetcode40:组合总和 II

排列

leetcode131. 分割回文串

93. 复原IP地址

leetcode22：22. 括号生成

回溯解数独

 

---

子集：

90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

注意：本题子集中剪枝条件 if (i != start && nums[i] == nums[i - 1])就可以过滤掉本层相邻重复元素，而因为已经用i = start去除了已选过元素，再通过i !=start 可以放过本层第一个与上层相同的元素。

f. 而求排列是通过剪枝条件if (i > 0 && nums[i] == nums[i - 1] && visit[i - 1] == 0)中的visit[i - 1] == 0来达到只过滤本层重复元而放过下一层首个重复元。CSDN

// 子集. 回溯过过程中，记录树上所有出现的节点，因此没有收敛条件, 所有path都记录到res

// 有重复元素，结果集不能有重复. 因此(1)先要对输入进行排序 (2)然后遍历候选集时，对相同值的候选点只选一次，剪掉后面分支

    // lc90
/* 思路：相同层相同元素剪枝: (start != i) + (nums[i] == nums[i - 1])组合判断[]1                     2               2剪[{1}, 2]   [{1}, 2]剪   [{2}, 2][{1, 2}, 2]
*/// 有重复元素，结果集不能有重复. 因此(1)先要对输入进行排序 (2)然后遍历候选集时，对相同值的候选点只选一次，剪掉后面分支vector<vector<int>> subsetsWithDup(vector<int>& nums){vector<vector<int>> res;if (nums.size() == 0) {return res;}sort(nums.begin(), nums.end());vector<int> path;size_t start = 0;BackTrack(nums, start, path, res);return res;}void BackTrack(vector<int> &sets, int start, vector<int> &path, vector<vector<int>> &res){// 因为记录树上所有节点, 所以无需收敛条件。这种遍历到最后是只记录叶节点: if (start == sets.size())res.push_back(path);for (int i = start; i < sets.size(); i++) {if (i != start && sets[i] == sets[i - 1]) { // 剪枝continue;}path.push_back(sets[i]);BackTrack(sets, i + 1, path, res);path.pop_back();}}

组合

leetcode17(中等): 电话号码的字母组合

class Solution {
public:vector<string> letterCombinations(string digits){vector<string> result;if (digits.size() == 0) {return result;}string path; // 路径map<char, string> digitsStr = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};size_t depth = 0;BackTrack(result, digits, digitsStr, depth, path);return result;}void BackTrack(vector<string> &result, string &digits, map<char, string> &digitsStr,  size_t depth, string path){if (depth == digits.size()) {result.push_back(path);return;}string curDigitStr = digitsStr[digits[depth]];for (size_t i = 0; i < curDigitStr.size(); i++) {path.push_back(curDigitStr[i]);BackTrack(result, digits, digitsStr, depth + 1, path);path.pop_back();}}
};

leetcode39 组合总和:

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:[ [7], [2,2,3]]

题解：

1，正序相加思想：

就是找相加和为target的所有组合，重点是去重。

2，逆序相减思想：

// 解集不能包含重复的组合: 对输入排序
// candidates 中的数字可以无限制重复被选取: 递归调用时传i
// 所有数字（包括 target）都是正整数。
// 剪枝：(1)start去除上面层已选保证向后选择 (2) 用start != 0 && num[i] == num[i-1]或遍历候选集前赋值负值，
//       候选点逐个比较并赋值 来进行去除本层重复元素(candidate元素独一无二，因此剪枝(2)没必要)。(3) 中剪枝 (candidates[i] > gap) then break
// 收敛：gap == 0;

力扣

题解中是以子集的思想解题的，即：候选数组里有 2 ，如果找到了 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；依次循环下去。

题解中递归树如下图(图借用liweiwei1419的题解中图片)：

去重复：

    在搜索的时候，需要设置搜索起点的下标 begin ，由于一个数可以使用多次，下一层的结点从这个搜索起点开始搜索；
    在搜索起点 begin 之前的数因为以前的分支搜索过了，所以一定会产生重复。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:vector<vector<int>> combinationSum(vector<int> &candidates, int target) {vector<vector<int>> result;vector<int> path;int pathSum = 0;sort(candidates.begin(), candidates.end());int start = 0;TrackBack(result, candidates, path, pathSum, target, start);return result;}void TrackBack(vector<vector<int>> &result, vector<int> &candidates, vector<int> &path,int &pathSum, int target, int start){if (pathSum == target) {//vector<int> tmp(path);//sort(tmp.begin(), tmp.end());//if (find(result.begin(), result.end(), tmp) == result.end()) {result.push_back(path);//}return;}// if (pathSum + candidates[0] > target) {//     return;// }// 设置搜索起点，用于去除重复。重要for (int i = start; i < candidates.size(); i++) {if (pathSum + candidates[i] > target) {return;}path.push_back(candidates[i]);pathSum += candidates[i];TrackBack(result, candidates, path, pathSum, target, i);pathSum -= candidates[i];path.pop_back();}}
};// 逆序相减
class Solution1 {
public:// 解集不能包含重复的组合: 对输入排序// candidates 中的数字可以无限制重复被选取: 递归调用时传i// 所有数字（包括 target）都是正整数。// 剪枝：(1)start去除上面层已选保证向后选择 (2) 用start != 0 && num[i] == num[i-1]或遍历候选集前赋值负值，//       候选点逐个比较并赋值 来进行去除本层重复元素(candidate元素独一无二，因此剪枝(2)没必要)。(3) 中剪枝 (candidates[i] > gap) then break// 收敛：gap == 0;vector<vector<int>> combinationSum(vector<int> &candidates, int target) {vector<vector<int>> res;vector<int> path;int start = 0;sort(candidates.begin(), candidates.end());BackTrack(candidates, path, start, target, res);return res;}void BackTrack(vector<int> &candidates, vector<int> &path, int start, int gap, vector<vector<int>> &res){if (gap == 0) {res.push_back(path);return;}for (int i = start; i < candidates.size(); i++) {// if (start != i && candidates[i] == candidates[i - 1]) { // candidate元素独一无二, 无需去除本层重复元素//     continue;// }if (candidates[i] > gap) {break;}path.push_back(candidates[i]);BackTrack(candidates, path, i, gap - candidates[i], res);path.pop_back();}}
};

leetcode40:组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:[[1,2,2],[5]]

题解：

// 解集不能包含重复的组合: 对输入排序
// candidates中的每个数字在每个组合中只能使用一次: 递归调用时传i + 1
// 所有数字（包括 target）都是正整数：去除本层重复元素保留下层重复元可用，遍历候选集前赋值负值，候选点逐个比较并赋值
// 剪枝：(1)start去除上面层已选保证向后选择 (2) 去除本层重复元素保留下层重复元：法2：用start != 0 && num[i] == num[i-1]或法1：遍历候选集前赋值负值，候选点逐个比较并赋值(3) 中剪枝 (candidates[i] > gap) then break
// 收敛：gap == 0;

去除本层重复元素保留下层重复元见链接重点4：https://blog.csdn.net/u011764940/article/details/105592965

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:vector<vector<int>> combinationSum(vector<int> &candidates, int target) {vector<vector<int>> result;vector<int> path;int pathSum = 0;sort(candidates.begin(), candidates.end());int start = 0;TrackBack(result, candidates, path, pathSum, target, start);return result;}void TrackBack(vector<vector<int>> &result, vector<int> &candidates, vector<int> &path,int &pathSum, int target, int start){if (pathSum == target) {result.push_back(path);return;}int thisLevelVal = INT_MIN;for (int i = start; i < candidates.size(); i++) {// 小剪枝if (candidates[i] == thisLevelVal) {continue;}thisLevelVal = candidates[i];// 大剪枝if (pathSum + candidates[i] > target) {return;}path.push_back(candidates[i]);pathSum += candidates[i];TrackBack(result, candidates, path, pathSum, target, i + 1);pathSum -= candidates[i];path.pop_back();}}
};class Solution1 {
public:// 解集不能包含重复的组合: 对输入排序// candidates中的每个数字在每个组合中只能使用一次: 递归调用时传i + 1// 所有数字（包括 target）都是正整数：去除本层重复元素保留下层重复元可用，遍历候选集前赋值负值，候选点逐个比较并赋值// 剪枝：(1)start去除上面层已选保证向后选择 (2) 去除本层重复元素保留下层重复元：用start != 0 && num[i] == num[i-1]或遍历候选集前赋值负值，//       候选点逐个比较并赋值(3) 中剪枝 (candidates[i] > gap) then break// 收敛：gap == 0;vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {vector<vector<int>> res;vector<int> path;int start = 0;sort(candidates.begin(), candidates.end());BackTrack(candidates, path, start, target, res);return res;}void BackTrack(vector<int> &candidates, vector<int> &path, int start, int gap, vector<vector<int>> &res){if (gap == 0) {res.push_back(path);return;}int levVal = -1; // 去除本层重复元，保留下层重复元。法1步骤1for (int i = start; i < candidates.size(); i++) {// if (start != i && candidates[i] == candidates[i - 1]) { // 去除本层重复元，保留下层重复元。法2//     continue;// }if (candidates[i] == levVal) { // 去除本层重复元，保留下层重复元。法1步骤2continue;}if (candidates[i] > gap) {break;}levVal = candidates[i]; // 去除本层重复元，保留下层重复元。法1步骤3path.push_back(candidates[i]);BackTrack(candidates, path, i + 1, gap - candidates[i], res);path.pop_back();}}
};

排列

leetcode131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

思路：每一步都可以判断中间结果是否为合法结果，必须走到底部才能完全判断一次path分割的所有子串是否合法(本题是所有子串都满足回文串)，回溯法。

//确定候选集：可选子串组合集。从start索引开始，对i for (i=start: i<s.size)，可选i - start + 1长度的子串。进入下一层时start = i+1。 如第一层可选子串集合[a, aa, aab]

// 收敛条件：子串的pos点到了原始串的最后，无子串可选

// 可否剪枝：当前子串是否是回文

注：函数传递原始串s时一定要传引用，大幅降耗时。

class Solution {
public:// 排列// 候选集：可选子串组合集. 如第一层可选子串集合[a, aa, aab]// 收敛条件：子串的pos点到了原始串的最后，无子串可选// 可否剪枝：当前子串是否是回文vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> path;// s 和 start组成候选集Backtrack(s, 0, path, res);return res;}void Backtrack(string &s, int start, vector<string> &path, vector<vector<string>> &res){//收敛条件if (start == s.size()) {res.push_back(path);}// 遍历可选集for (int i = start; i < s.size(); i++) {// string subStr = s.substr(start, i - start + 1); // 获得子串的动作放到剪枝之后if (IsPalindrome(s, start, i)) {path.push_back(s.substr(start, i - start + 1));Backtrack(s, i + 1, path, res);// 恢复现场path.pop_back();}}}// 共3中方法：1, 双指针前后向中间滑动. 2, 栈入栈2/strlen次，依次出栈和剩余串比较. 3, 反转后和自己比// 这里写法不好bool IsPalindrome1(string str){if (str.size() == 0) {return false;}// 双指针int start = 0;int end = str.size() - 1;while (start <= end) {if (str[start] != str[end]) {return false;}if (start == end) {break;}start++;end--;}return true;}bool IsPalindrome(string &str, int start, int end){// if (str.size() == 0) {//     return false;// }// 双指针// int start = 0;// int end = str.size() - 1;while (start < end && str[start] == str[end]) {start++;end--;}return start >= end;}
};

93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

思路：同131. 分割回文串，每一步都可以判断中间结果是否为合法结果，必须走到底部才能完全判断一次path分割的所有子串是否合法(本题是所有子串都满足回文串)，回溯法。

确定候选集：从start索引开始，对i for (i = start: i < start + 3)(ip中每段最多3个数字，因此候选集最多包含三个元素），可选i - start + 1长度的子串。

剪枝：候选集外的大剪枝(根据当前索引start判断剩余字符串长度，若不合法直接return，不在进入候选集)，和候选集内的小剪枝(候选集三个元素中某个不满足ip的0-255数组要求，continue选下一个元素）。

注意特殊剪枝：ip中某段，不允许前缀0，但允许单个0。

// 收敛：start到s的最后

// 候选集： 对start, 可以取 1 2 3个字符的子串

// 剪枝: 1, 子串大于255。2，剩余的串长度不满足全串分割为4个段。3，剪掉0x,0xx这种的分段

// 如何退出递归：(1)候选集的起始点需要与输入串的可选集大小相关联i < start + 3 && i < s.size()，保证退出递归调用。 或(2)写单独的终止条件start > s.size(), (3)在大剪枝判断处remainLen < 4 - subStrNum也能保证退出递归

注：解法2/3是把截取子串放在剪枝之后，可以优化性能。其中解法2的剪掉0x,0xx分段更直观。

解法1：

class Solution {
public:// 收敛：start到s的最后// 候选集： 对start, 可以取 1 2 3个字符的子串// 剪枝: 1, 子串大于255。2，剩余的串长度不满足全串分割为4个段。3，剪掉0x,0xx这种的分段// 如何退出递归：(1)候选集的起始点需要与输入串的可选集大小相关联i < start + 3 && i < s.size()，保证退出递归调用// 或(2)写单独的终止条件start > s.size(), (3)在大剪枝判断处remainLen < 4 - subStrNum也能保证退出递归vector<string> restoreIpAddresses(string s) {vector<string> res;vector<string> path;BackTrack(s, 0, path, res);return res;}void BackTrack(string &s, int start, vector<string> &path, vector<string> &res){// 终止条件if (start > s.size()) {return;}// 收敛条件if (start == s.size() && path.size() == 4) {string thisRes = path[0];for (int i = 1; i < path.size(); i++) {thisRes += '.' + path[i];}res.push_back(thisRes);return;}// 大剪枝：剩余的串长度不满足全串分割为4个段int subStrNum = path.size();int remainLen = s.size() - start;if (remainLen > (4 - subStrNum) * 3 || remainLen < 4 - subStrNum) {return;}for (int i = start; i < start + 3; i++) {string subStr = s.substr(start, i - start + 1);// 中剪枝, 剪掉起始数字为0且subStr.size()大于1的数，即剪掉0x,0xx这种. breakif (subStr[0] == '0' and subStr.size() > 1) {break;}if (stoi(subStr) > 255) { //小剪枝，剪掉数字大于255的数continue;}path.push_back(subStr);BackTrack(s, i + 1, path, res);path.pop_back();}}
};

 解法2：

class Solution1 {
public:vector<string> restoreIpAddresses(string s) {vector<string> result;vector<string> ip;int start = 0;Dfs(s, result, ip, start);return result;}void Dfs(string& s, vector<string>& result, vector<string>& ip, int start) {if (ip.size() == 4 && start == s.size()) { // 终止条件result.push_back(ip[0] + "." + ip[1] + "." + ip[2] + "." + ip[3]);return;}// 大剪枝, returnif (s.size() - start > (4 - ip.size()) * 3) {return;}if (s.size() - start < 4 - ip.size()) {return;}int num = 0;// 候选集每次1~3个数字for (size_t i = start; i < start + 3; i++) {// 中剪枝, break, 去掉ip各段首数字为0的场景if (i > start && num == 0) {break;}num = num * 10 + s[i] - '0';// 小剪枝, continueif (num < 0 || num > 255) {continue;}ip.push_back(s.substr(start, i - start + 1));Dfs(s, result, ip, i + 1);ip.pop_back();}}
};

解法3：

class Solution2 {
public:vector<string> restoreIpAddresses(string s) {vector<string> result;vector<string> ip;int start = 0;Dfs(s, result, ip, start);return result;}void Dfs(string& s, vector<string>& result, vector<string>& ip, int start) {if (ip.size() == 4 && start == s.size()) { // 终止条件result.push_back(ip[0] + "." + ip[1] + "." + ip[2] + "." + ip[3]);return;}// 大剪枝, returnif (s.size() - start > (4 - ip.size()) * 3) {return;}if (s.size() - start < 4 - ip.size()) {return;}int num = 0;// 候选集每次1~3个数字for (size_t i = start; i < start + 3; i++) {num = num * 10 + s[i] - '0';// 小剪枝, continueif (num < 0 || num > 255) {continue;}ip.push_back(s.substr(start, i - start + 1));Dfs(s, result, ip, i + 1);ip.pop_back();// 中剪枝, break, 去掉ip各段首数字为0的场景if (num == 0) {break;}}}
};

leetcode22：22. 括号生成

注意：// 剪枝2：剪掉不符合括号条件的分支

注：这两个解法都有回溯算法解子集、组合、排序_u011764940的博客-CSDN博客重点6，遍历候选集起始索引用0以start与候选集大小判断收敛的混搭问题。最好改掉。

class Solution1 {
public:vector<string> generateParenthesis(int n) {string collects(n, '(');string collectsRight(n, ')');collects.append(collectsRight);vector<string> result;string path;vector<bool> visited(2*n, false);dfs(result, collects, path, visited, 0);return result;}void dfs(vector<string> &result, string &collects, string &path,  vector<bool> &visited, int start){if (start == collects.length()) {result.push_back(path);return;}for (size_t i = 0; i < collects.size(); i++) {if (visited[i] == true) {continue;}// 同一层去重，剪枝if (i > 0 && collects[i] == collects[i - 1] && visited[i - 1] == false) {continue;}// 剪枝if (collects[i] == ')' &&count(path.begin(), path.end(), '(') <= count(path.begin(), path.end(), ')')) {continue;}path.push_back(collects[i]);visited[i] = true;dfs(result, collects, path, visited, i + 1);visited[i] = false;path.pop_back();}}
};class Solution {
public:vector<string> generateParenthesis(int n) {string collects(n, '(');string collectsRight(n, ')');collects.append(collectsRight);vector<string> result;string path;vector<bool> visited(2*n, false);unordered_map<char, int> pathBraceCount;pathBraceCount['('] = 0;pathBraceCount[')'] = 0;dfs(result, collects, path, visited, 0, pathBraceCount);return result;}void dfs(vector<string> &result, string &collects, string &path,  vector<bool> &visited,size_t start, unordered_map<char, int>& pathBraceCount){if (start == collects.size()) {result.push_back(path);return;}for (size_t i = 0; i < collects.size(); i++) {if (visited[i] == true) {continue;}// 同一层去重，剪枝if (i > 0 && collects[i] == collects[i - 1] && visited[i - 1] == false) {continue;}// 剪枝if (collects[i] == ')' && pathBraceCount[')'] >= pathBraceCount['(']) {return;}path.push_back(collects[i]);visited[i] = true;pathBraceCount[collects[i]]++;dfs(result, collects, path, visited, i + 1, pathBraceCount);visited[i] = false;pathBraceCount[collects[i]]--;path.pop_back();}}
};

回溯解数独

剪枝条件

法1：回溯解法，但剪枝低效。剪枝判断函数IsValid中进行了朴素搜索，根因是没有进行约束编程，即没有放置每个数字时都设置约束

// 思路1：回溯-排列，求一个解（时间复杂度高，每次递归找第一个'.'时存在大量重复动作）

// 收敛条件：最后一行最后一个数满足数独定义

// 候选集: 每个位置都可以从[0, 1, ..., n]选一个数

// 注：1, 需要两层遍历取每一个点, 对每一个点遍历候选集

// 2, 一个解的结果是传入的board本身的部分填充, 候选点直接选入board。

// 3, 几个return的注意和说明，以及需要回溯函数返回bool的原因。回溯（或深搜）里一个可行解的回溯（dfs）函数本身是在满足收敛条件时return并在递归调用处持续return: 若返回void则通过引用带出一个解的结果; 若返回bool则是题目要求是否有可行解。而本题需要即返回bool又要用引用带出那一个解的结果。因为：(1) 满足收敛条件时需要return，(2) 对某位置点遍历完候选集都不满足数独定义时, 说明该位置点之前的点不满足条件, 需要return, 以对之前的点恢复现场尝试下一候选点。综合(1)(2)的两种return需要进行区分，因此需要返回bool。收敛的return ture需要在递归调用处持续返回true, 遍历完候选集不满足数独定义的return false则需要在递归调用后恢复现场并尝试下一候选点。

解法1：
class Solution2 {
public:// 思路1：回溯-排列，求一个解（时间复杂度高，每次递归找第一个'.'时存在大量重复动作）// 收敛条件：最后一行最后一个数满足数独定义// 候选集: 每个位置都可以从[0, 1, ..., n]选一个数// 注：1, 需要两层遍历取每一个点, 对每一个点遍历候选集// 2, 一个解的结果是传入的board本身的部分填充, 候选点直接选入board。// 3, 几个return的注意和说明，以及需要回溯函数返回bool的原因。回溯（或深搜）里一个可行解的回溯（dfs）函数本身是在满足收敛// 条件时return并在递归调用处持续return: 若返回void则通过引用带出一个解的结果; 若返回bool则是题目要求是否有可行解。而本题// 需要即返回bool又要用引用带出那一个解的结果。因为：(1) 满足收敛条件时需要return，(2) 对某位置点遍历完候选集都不满足数独// 定义时, 说明该位置点之前的点不满足条件, 需要return, 以对之前的点恢复现场尝试下一候选点。综合(1)(2)的两种return需要进行// 区分，因此需要返回bool。收敛的return ture需要在递归调用处持续返回true, 遍历完候选集不满足数独定义的return false则需要// 在递归调用后恢复现场并尝试下一候选点。void solveSudoku(vector<vector<char>>& board) {if (board.size() == 0) {return;}BackTrack(board);}bool BackTrack(vector<vector<char>>& board){int m = board.size();int n = board[0].size();// 两层循环遍历对每个位置点for (int i = 0; i < m; i++) {        // 每次递归调用找BackTrack'.'的当前位置时存在大量重复动作startfor (int j = 0; j < n; j++) {if (isdigit(board[i][j])) {continue;}                            // 每次递归调用找BackTrack'.'的当前位置时存在大量重复动作end// 当前位置点的候选集for (int k = 0; k < m; k++) {if (!IsVaid(k + '1', i, j, board)) {continue;}// board选择候选点board[i][j] = k + '1';// // 收敛条件 放置位置1'// if (i == m - 1 && j == n - 1) {//     return true;// }if (BackTrack( board)) {// 已收敛, 持续返回return true;}// board恢复现场board[i][j] = '.';}// 当前位置遍历完候选集都不符合数独定义, 需return false去把前一个位置给恢复并尝试下一候选点return false;}}// 收敛条件 放置位置1return true;}bool IsVaid(char k, int curRow, int curCol, vector<vector<char>>& board){// 行int row = board.size();int col = board[0].size();for (int i = 0; i < row; i++) {if (board[i][curCol] == k) {return false;}}// 列for (int i = 0; i < col; i++) {if (board[curRow][i] == k) {return false;}}// boxfor (int i = (curRow / 3) * 3; i < (curRow / 3) * 3 + 3; i++) {for (int j = (curCol / 3) * 3; j < (curCol / 3) * 3 + 3; j++) {if (board[i][j] == k) {return false;}}}return true;}
};解法2：
class Solution {
public:void solveSudoku(vector<vector<char>>& board){MysolveSudoku(board);}bool MysolveSudoku(vector<vector<char>>& board){for (size_t i = 0; i < board.size(); i++) {for (size_t j = 0; j < board.size(); j++) {if (board[i][j] == '.') {for (size_t k = 0; k < board.size(); k++) {board[i][j] = '1' + k;if (IsValid(board, i, j) && MysolveSudoku(board)) {return true;}board[i][j] = '.';}return false;}}}return true;}bool IsValid(vector<vector<char>>& board, size_t x, size_t y){// 检查行for (size_t i = 0; i < 9; i++) {if (i != x && board[i][y] == board[x][y]) {return false;}}// 检查列for (size_t j = 0; j < 9; j++) {if (j != y && board[x][j] == board[x][y]) {return false;}}// 检查boxfor (size_t i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++) {for (size_t j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++) {if ((i != x || j != y) && board[i][j] == board[x][y]) {return false;}}}return true;}
};

法2：回溯解法，剪枝高效。进行了约束编程。

借用官方解答图：力扣

    // 思路2：

    // 整体思路与思路1相同。找唯一一个解，需要在收敛时return，又因为要回溯在候选集未找到满足数独定义时需要return到上一位置恢复现场并

    // 尝试下一候选点，因此回溯函数返回bool，收敛时return true, 在候选集未找到合适的候选点时return false.

    // 注：

    // (1)回溯函数开始处直接找到当前board中第一个'.'位置 + 判断收敛。为了避免每次递归都从[0, 0]位置找第一个'.'点，采用传row和col的方式，然后再开始处直接++col处理。

    // (2)剪枝：以三个visit进行hash棋盘已出现数字在各行、列、box是否已被选过，就是备忘录。已经是数独定义了。并不需要再通过专门的遍历进行数独判断。

    //行，列，小格内某数字是否已被选过(填过)

class Solution {
public://行，列，小格内某数字是否已填标记bool visitRow[9][9] = { false };bool visitCol[9][9] = { false };bool visitBox[9][9] = { false };int num = 0;void solveSudoku(vector<vector<char>>& board) {//先记录表格中的初始状态for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.'){visitRow[i][ board[i][j] - '1'] = true;visitCol[j][ board[i][j] - '1'] = true;visitBox[ (i / 3) * 3 + j / 3 ][ board[i][j] - '1'] = true;}}}backTrack(board, 0, 0);}bool backTrack(vector<vector<char>>& board, int row,int col){// 找到没填的while(board[row][col] != '.'){if(++col >= 9){col = 0;row++;}// 填满了; 收敛条件 if(row >= 9)return true;}// 候选集'0' - '9'for(int i = 0; i < 9; i++){int boxIndex = (row / 3) * 3 + col / 3;//已经填了, 小剪枝if(visitRow[row][i] || visitCol[col][i] || visitBox[boxIndex][i])continue;// 选入board[row][col] = i + '1';visitRow[row][i] = true;visitCol[col][i] = true;visitBox[boxIndex][i] = true;if(backTrack(board, row, col)){return true;}else{//最后无法填满, 恢复现场board[row][col] = '.';visitRow[row][i] = false;visitCol[col][i] = false;visitBox[boxIndex][i] = false;}}return false;}
};

这篇关于回溯-子集_组合_排序_练习的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---