A summary of backtracking related problems from LeetCode with solutions in C++.
组合问题: N个数里面按一定规则找出k个数的集合
切割问题: 一个字符串按一定规则有几种切割方式
子集问题: 一个N个数的集合里有多少符合条件的子集
排列问题: N个数按一定规则全排列，有几种排列方式
棋盘问题: N皇后，解数独等等
Template of Backtracking Algorithm
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择: 本层集合中元素(树中节点孩子的数量就是集合的大小)) {
// 处理节点;
backtracking(路径，选择列表); // 递归
// 回溯, 撤销处理结果
}
}
Problems:
77. Combinations
216. Combination Sum III
17. Letter Combinations of a Phone Number
39. Combination Sum
40. Combination Sum II
131. Palindrome Partitioning
93. Restore IP Addresses
78. Subsets
90. Subsets II
491. Non-decreasing Subsequences
46. Permutations
47. Permutations II
332. Reconstruct Itinerary
51. N-Queens
37. Sudoku Solver
Problem: Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.
Case 1: Input: n = 4, k = 2, Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Case 2: Input: n = 1, k = 1, Output: [[1]]
正常操作
剪枝优化
如果n = 4, k = 4的话, 那么第一层for循环的时候, 从元素2开始的遍历都没有意义了。 在第二层for循环, 从元素3开始的遍历都没有意义了。所以, 可以剪枝的地方就在递归中每一层的for循环所选择的起始位置
class Solution {
private:
vector<int> path; // 用来存放符合条件结果
vector<vector<int>> result; // 存放符合条件结果的集合
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path); // path是叶子节点处的集合
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归
path.pop_back(); // 回溯, 撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
path.clear(); // 可以不写
result.clear(); // 可以不写
backtracking(n, k, 1);
return result;
}
};
// 剪枝优化
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
path.push_back(i); // 处理节点
backtracking(n, k, i + 1);
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
path.clear();
result.clear();
backtracking(n, k, 1);
return result;
}
};
Problem: Find all valid combinations of k numbers that sum up to n such that the following conditions are true: (1) Only numbers 1 through 9 are used. (2) Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Case 1: Input: k = 3, n = 7, Output: [[1,2,4]]
Case 2: Input: k = 3, n = 9, Output: [[1,2,6],[1,3,5],[2,3,4]]
Case 3: Input: k = 4, n = 1, Output: []
本题k相当于树的深度, 9(因为整个集合就是9个数)就是树的宽度。例如 k = 2, n = 4的话, 就是在集合[1,2,3,4,5,6,7,8,9]中求 k(个数) = 2, n(和) = 4的组合
剪枝优化
已选元素总和如果已经大于n(图中数值为4)了, 那么往后遍历就没有意义了, 直接剪掉
class Solution {
private:
vector<int> path; // 符合条件的结果
vector<vector<int>> result; // 存放结果集
// targetSum: 目标和, 题目中的n
// k: 题目中要求k个数的集合
// sum: 已经收集的元素的总和, path里元素的总和
// startIndex: 下一层for循环搜索的起始位置
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (path.size() == k) {
if (sum == targetSum) { result.push_back(path); }
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
for (int i = startIndex; i <= 9; i++) {
sum += i; // 处理
path.push_back(i); // 处理
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1);
return result;
}
};
// 剪枝版
class Solution {
private:
vector<int> path; // 符合条件的结果
vector<vector<int>> result; // 存放结果集
// targetSum: 目标和, 题目中的n
// k: 题目中要求k个数的集合
// sum: 已经收集的元素的总和, path里元素的总和
// startIndex: 下一层for循环搜索的起始位置
void backtracking(int targetSum, int k, int sum, int startIndex) {
// 剪枝操作
if (sum > targetSum) {
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
if (path.size() == k) {
if (sum == targetSum) { result.push_back(path); }
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
// 剪枝操作
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
sum += i; // 处理
path.push_back(i); // 处理
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1);
return result;
}
};
3. 17. Letter Combinations of a Phone Number
Problem: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Case 1: Input: digits = “23”, Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
Case 2: Input: digits = “”, Output: []
Case 3: Input: digits = “2”, Output: [“a”,”b”,”c”]
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
string s;
vector<string> result;
// index: 当前遍历到哪个数字了
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
// 在叶子节点收获结果
result.push_back(s);
return;
}
int digit = digits[index] - '0'; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]); // 处理
backtracking(digits, index + 1); // 递归, 注意index+1, 一下层要处理下一个数字了
s.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) { return result; }
backtracking(digits, 0);
return result;
}
};
Problem: Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Case 1: Input: candidates = [2,3,6,7], target = 7, Output: [[2,2,3],[7]]
Case 2: Input: candidates = [2,3,5], target = 8, Output: [[2,2,2,2],[2,3,3],[3,5]]
Case 3: Input: candidates = [2], target = 1, Output: []
剪枝优化 对总集合排序之后, 如果下一层的sum(就是本层的sum + candidates[i])已经大于target, 就可以结束本轮for循环的遍历
// 函数参数及返回值
// 确定终止条件
// 单层搜索逻辑
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum > target) { return; }
if (sum == target) {
result.push_back(path); // path is one of the solutions
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 不用i+1了, 表示可以重复读取当前的数
sum -= candidates[i]; // 回溯
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, target, 0, 0);
return result;
}
};
// 剪枝优化
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 需要排序
backtracking(candidates, target, 0, 0);
return result;
}
};
Problem: Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.
Case 1: Input: candidates = [10,1,2,7,6,1,5], target = 8,
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Case 2: Input: candidates = [2,5,2,1,2], target = 5,
Output: [[1,2,2],[5]]
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex,
vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// used[i - 1] == true, 说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false, 说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
// 这里是i+1, 每个数字在每个组合中只能使用一次
backtracking(candidates, target, sum, i + 1, used);
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(), false);
// 首先把给candidates排序, 让其相同的元素都挨在一起
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
};
6. 131. Palindrome Partitioning
Problem: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Case 1: Input: s = “aab”, Output: [[“a”,”a”,”b”],[“aa”,”b”]]
Case 2: Input: s = “a”, Output: [[“a”]]
class Solution {
private:
vector<string> path;
vector<vector<string>> result;
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) { return false; }
}
return true;
}
void backtracking (const string& s, int startIndex) {
// 如果startIndex已经大于s的大小, 说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
// 是回文子串
if (isPalindrome(s, startIndex, i)) {
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程, 弹出本次已经填在的子串
}
}
public:
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return result;
}
};
Problem: A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Case 1: Input: s = “25525511135”, Output: [“255.255.11.135″,”255.255.111.35”]
Case 2: Input: s = “0000”, Output: [“0.0.0.0”]
Case 3: Input: s = “101023”, Output: [“1.0.10.23″,”1.0.102.3″,”10.1.0.23″,”10.10.2.3″,”101.0.2.3”]
// 段位以0为开头的数字不合法
// 段位里有非正整数字符不合法
// 段位如果大于255了不合法
class Solution {
private:
vector<string> result;
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
if (start > end) { return false; }
// 0开头的数字不合法
if (s[start] == '0' && start != end) { return false; }
int num = 0;
for (int i = start; i <= end; i++) {
// 遇到非数字字符不合法
if (s[i] > '9' || s[i] < '0') { return false; }
num = num * 10 + (s[i] - '0');
// 如果大于255了不合法
if (num > 255) { return false; }
}
return true;
}
// startIndex : 搜索的起始位置
// pointNum : 添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
// 逗点数量为3时, 分隔结束
if (pointNum == 3) {
// 判断第四段子字符串是否合法, 如果合法就放进result中
// [start, end]
if (isValid(s, startIndex, s.size() - 1)) { result.push_back(s); }
return;
}
for (int i = startIndex; i < s.size(); i++) {
// 判断 [startIndex,i] 这个区间的子串是否合法
if (isValid(s, startIndex, i)) {
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
pointNum--; // 回溯
s.erase(s.begin() + i + 1); // 回溯删掉逗点
} else { break; } // 不合法, 直接结束本层循环
}
}
public:
vector<string> restoreIpAddresses(string s) {
// 算是剪枝了
if (s.size() < 4 || s.size() > 12) { return result; }
backtracking(s, 0, 0);
return result;
}
};
8. 78. Subsets
Problem: Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
Case 1: Input: nums = [1,2,3], Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Case 2: Input: nums = [0], Output: [[],[0]]
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex) {
// 收集子集, 要放在终止添加的上面, 否则会漏掉自己
result.push_back(path);
// 终止条件可以不加
if (startIndex >= nums.size()) { return; }
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
Problem: Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
Case 1: Input: nums = [1,2,2], Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Case 2: Input: nums = [0], Output: [[],[0]]
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// used[i - 1] == true, 说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false, 说明同一树层candidates[i - 1]使用过
// 而我们要对同一树层使用过的元素进行跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
};
10. 491. Non-decreasing Subsequences
Problem: Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.
Case 1: Input: nums = [4,6,7,7], Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Case 2: Input: nums = [4,4,3,2,1], Output: [[4,4]]
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex) {
if (path.size() > 1) { result.push_back(path); }
// 这里使用数组来进行去重操作, 题目说数值范围[-100, 100]
int used[201] = {0};
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums[i] < path.back()) || used[nums[i] + 100] == 1) {
continue;
}
used[nums[i] + 100] = 1; // 记录这个元素在本层用过了, 本层后面不能再用了
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
11. 46. Permutations
Problem: Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Case 1: Input: nums = [1,2,3], Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Case 2: Input: nums = [0,1], Output: [[0,1],[1,0]]
Case 3: Input: nums = [1], Output: [[1]]
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组, 到达叶子节点
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// path里已经收录的元素, 直接跳过
if (used[i] == true) { continue; }
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
Problem: Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Case 1: Input: nums = [1,1,2], Output: [[1,1,2],[1,2,1],[2,1,1]]
Case 2: Input: nums = [1,2,3], Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组, 到达叶子节点
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true, 说明同一树枝nums[i - 1]使用过
// used[i - 1] == false, 说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
13. 332. Reconstruct Itinerary
Problem: You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”]. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Case 1: Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]], Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]
Case 2: Input: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]], Output: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
if (result.size() == ticketNum + 1) { return true; }
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
// 记录到达机场是否飞过了
if (target.second > 0 ) {
result.push_back(target.first);
target.second--;
if (backtracking(ticketNum, result)) { return true; }
result.pop_back();
target.second++;
}
}
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
targets.clear();
// For debugging
vector<string> startPlace;
vector<string> result;
for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
startPlace.push_back(vec[0]);
}
// For debugging
for (auto sPlace : startPlace) {
for (pair<const string, int>& target : targets[sPlace]) {
std::cout << sPlace << ", "<< target.first << ", " << target.second << std::endl;
}
}
result.push_back("JFK"); // 起始机场
backtracking(tickets.size(), result);
return result;
}
};
14. 51. N-Queens
Problem: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
Case 1: Input: n = 4, Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
Case 2: Input: n = 1, Output: [[“Q”]]
class Solution {
private:
vector<vector<string>> result;
bool isValid(int row, int col, vector<string>& chessboard, int n) {
// 检查列
for (int i = 0; i < row; i++) { // 这是一个剪枝
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查45度角是否有皇后
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查135度角是否有皇后
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
// n 为输入的棋盘大小, row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < n; col++) {
// 验证合法就可以放
if (isValid(row, col, chessboard, n)) {
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
std::vector<std::string> chessboard(n, std::string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};
Problem : Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules :
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.
The ‘.’ character indicates empty cells.
Case 1:
Input: board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”],[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
Output: [[“5″,”3″,”4″,”6″,”7″,”8″,”9″,”1″,”2”],[“6″,”7″,”2″,”1″,”9″,”5″,”3″,”4″,”8”],[“1″,”9″,”8″,”3″,”4″,”2″,”5″,”6″,”7”],[“8″,”5″,”9″,”7″,”6″,”1″,”4″,”2″,”3”],[“4″,”2″,”6″,”8″,”5″,”3″,”7″,”9″,”1”],[“7″,”1″,”3″,”9″,”2″,”4″,”8″,”5″,”6”],[“9″,”6″,”1″,”5″,”3″,”7″,”2″,”8″,”4”],[“2″,”8″,”7″,”4″,”1″,”9″,”6″,”3″,”5”],[“3″,”4″,”5″,”2″,”8″,”6″,”1″,”7″,”9”]]
Explanation: The input board is shown above and the only valid solution is shown below:
class Solution {
private:
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
// 判断行里是否重复
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
// 判断列里是否重复
for (int j = 0; j < 9; j++) {
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
// 判断9方格里是否重复
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) { // 遍历行
for (int j = 0; j < board[0].size(); j++) { // 遍历列
if (board[i][j] == '.') {
for (char k = '1'; k <= '9'; k++) { // (i,j) 这个位置放k是否合适
if (isValid(i, j, k, board)) {
board[i][j] = k; // 放置k
if (backtracking(board)) { return true; } // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯, 撤销k
}
}
return false; // 9个数都试完了, 都不行, 那么就返回false
}
}
}
return true; // 遍历完没有返回false, 说明找到了合适棋盘位置了
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};