回溯算法主要是三个题型组合子集排序大致框架都是 确定递归函数的参数递归终止条件单层递归逻辑回溯算法用于解决for循环多的问题本质就是递归本文所使用的代码风格都是完整输入输出函数调用接口和具体实现用两个函数表达就这么几种题型理解之后会发现还是很简单的就像填空题一样无非是怎么处理重复问题题目要什么1. 1-n中k个的组合给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int n, int k, int startIndex, vectorint cur, vectorvectorint res) { if (cur.size() k) { res.push_back(cur); return; } for (int i startIndex; i n - (k - cur.size()) 1; i) { cur.push_back(i); Combine_Implement(n, k, i 1, cur, res); cur.pop_back(); } } // 接口函数 vectorvectorint Combine_jiekou(int n, int k) { vectorvectorint res; vectorint cur; Combine_Implement(n, k, 1, cur, res); return res; } int main() { int n, k; cin n k; vectorvectorint result Combine_jiekou(n, k); for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }剪枝2.组合的和#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int targetSum, int k, int sum, int startIndex, vectorint cur, vectorvectorint result) { if (sum targetSum) { // 剪枝操作 return; } if (cur.size() k) { if (sum targetSum) result.push_back(cur); return; // 如果cur.size() k 但sum ! targetSum 直接返回 } for (int i startIndex; i 9 - (k - cur.size()) 1; i) { // 剪枝 sum i; // 处理 cur.push_back(i); // 处理 Combine_Implement(targetSum, k, sum, i 1, cur, result); // 注意i1调整startIndex sum - i; // 回溯 cur.pop_back(); // 回溯 } } // 接口函数 vectorvectorint Combine_jiekou(int k, int n) { vectorvectorint result; vectorint cur; Combine_Implement(n, k, 0, 1, cur, result); return result; } int main() { int k, n; cin k n; vectorvectorint result Combine_jiekou(k, n); for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }3.组合的和II#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int target, int startIndex, int sum, vectorint candidates, vectorint cur, vectorvectorint result) { // 剪枝和超过目标值直接返回 if (sum target) { return; } // 找到一组有效组合 if (sum target) { result.push_back(cur); return; } // 遍历候选数字 for (int i startIndex; i candidates.size(); i) { // 剪枝当前数字加上后若超过目标则后续数字更大直接结束循环需提前排序 if (sum candidates[i] target) break; sum candidates[i]; // 处理 cur.push_back(candidates[i]); // 处理 // 关键允许重复选取递归时 startIndex 传 i不是 i 1 Combine_Implement(target, i, sum, candidates, cur, result); sum - candidates[i]; // 回溯 cur.pop_back(); // 回溯 } } // 接口函数 vectorvectorint Combine_jiekou(vectorint candidates, int target) { vectorvectorint result; vectorint cur; // 排序是剪枝的前提 sort(candidates.begin(), candidates.end()); Combine_Implement(target, 0, 0, candidates, cur, result); return result; } int main() { vectorint candidates; int target; // 示例输入模拟先读入数组长度再读入数组元素和目标值 int n; cin n; for (int i 0; i n; i) { int x; cin x; candidates.push_back(x); } cin target; vectorvectorint result Combine_jiekou(candidates, target); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }4.组合的和III#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int target, int startIndex, int sum, vectorint candidates, vectorint cur, vectorvectorint result) { // 找到一组有效组合 if (sum target) { result.push_back(cur); return; } // 剪枝和超过目标值直接返回 if (sum target) { return; } // 遍历候选数字 for (int i startIndex; i candidates.size(); i) { // 剪枝当前数字加上后若超过目标则后续数字更大直接结束循环依赖排序 if (sum candidates[i] target) break; // 同层去重排序后同一层递归中遇到相同的数字只取第一个避免重复组合 if (i startIndex candidates[i] candidates[i - 1]) continue; sum candidates[i]; // 处理 cur.push_back(candidates[i]); // 处理 // 关键每个数字只能使用一次递归时 startIndex 传 i 1 Combine_Implement(target, i 1, sum, candidates, cur, result); sum - candidates[i]; // 回溯 cur.pop_back(); // 回溯 } } // 接口函数 vectorvectorint Combine_jiekou(vectorint candidates, int target) { vectorvectorint result; vectorint cur; // 排序是剪枝和去重的前提 sort(candidates.begin(), candidates.end()); Combine_Implement(target, 0, 0, candidates, cur, result); return result; } int main() { vectorint candidates; int target; // 示例输入模拟先读入数组长度再读入数组元素和目标值 int n; cin n; for (int i 0; i n; i) { int x; cin x; candidates.push_back(x); } cin target; vectorvectorint result Combine_jiekou(candidates, target); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }5.子集#include bits/stdc.h using namespace std; // 递归实现函数 void Subsets_Implement(int startIndex, vectorint nums, vectorint cur, vectorvectorint result) { // 无目标和个数限制每次进入递归都将当前路径加入结果空集和所有中间状态均包含 result.push_back(cur); // 终止条件当起始索引越界时结束也可在for循环条件中自然结束 if (startIndex nums.size()) { return; } // 遍历候选数字 for (int i startIndex; i nums.size(); i) { // 处理选择当前数字 cur.push_back(nums[i]); // 递归注意 startIndex 传 i 1保证每个元素只选一次且顺序向后 Subsets_Implement(i 1, nums, cur, result); // 回溯撤销选择不选当前数字尝试同层的下一个数字 cur.pop_back(); } } // 接口函数 vectorvectorint Subsets_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; Subsets_Implement(0, nums, cur, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result Subsets_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }6.子集II#include bits/stdc.h using namespace std; // 递归实现函数 void Subsets_Implement(int startIndex, vectorint nums, vectorint cur, vectorvectorint result) { // 每次进入递归都将当前路径加入结果空集和所有中间状态均包含 result.push_back(cur); // 终止条件起始索引越界时结束 if (startIndex nums.size()) { return; } // 遍历候选数字 for (int i startIndex; i nums.size(); i) { // 同层去重排序后同一层递归中遇到相同的数字只取第一个避免重复子集 if (i startIndex nums[i] nums[i - 1]) continue; // 处理选择当前数字 cur.push_back(nums[i]); // 递归startIndex 传 i 1保证每个元素只选一次且顺序向后 Subsets_Implement(i 1, nums, cur, result); // 回溯撤销选择 cur.pop_back(); } } // 接口函数 vectorvectorint Subsets_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; // 排序是去重的前提 sort(nums.begin(), nums.end()); Subsets_Implement(0, nums, cur, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result Subsets_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }7.递增子集#include bits/stdc.h using namespace std; // 递归实现函数 void FindSubsequences_Implement(int startIndex, vectorint nums, vectorint cur, vectorvectorint result) { // 当前路径长度至少为2时加入结果 if (cur.size() 2) { result.push_back(cur); } // 终止条件起始索引越界时结束 if (startIndex nums.size()) { return; } // 用于同层去重注意不能排序需用哈希集合记录本层已使用的数字 unordered_setint used; // 遍历候选数字 for (int i startIndex; i nums.size(); i) { // 剪枝若当前数字小于路径末尾数字则无法构成递增序列 if (!cur.empty() nums[i] cur.back()) continue; // 同层去重本层已经使用过相同数字则跳过 if (used.find(nums[i]) ! used.end()) continue; used.insert(nums[i]); // 处理选择当前数字 cur.push_back(nums[i]); // 递归startIndex 传 i 1保证每个元素只选一次且顺序向后 FindSubsequences_Implement(i 1, nums, cur, result); // 回溯撤销选择 cur.pop_back(); } } // 接口函数 vectorvectorint FindSubsequences_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; // 注意不能排序因为题目要求保持原数组顺序的递增子序列 FindSubsequences_Implement(0, nums, cur, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result FindSubsequences_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }8.1-n中k个的全排序#include bits/stdc.h using namespace std; // 递归实现函数 void Permute_Implement(int k, vectorint cur, vectorbool used, vectorvectorint result) { // 当前路径长度达到k时加入结果 if (cur.size() k) { result.push_back(cur); return; } // 遍历候选数字1到n for (int i 1; i n; i) { // 剪枝如果当前数字已被使用则跳过 if (used[i]) continue; // 处理选择当前数字 cur.push_back(i); used[i] true; // 递归 Permute_Implement(k, cur, used, result); // 回溯撤销选择 cur.pop_back(); used[i] false; } } // 接口函数 vectorvectorint Permute_jiekou(int n, int k) { vectorvectorint result; vectorint cur; vectorbool used(n 1, false); Permute_Implement(k, cur, used, result); return result; } int main() { int n, k; // 读入n和k cin n k; vectorvectorint result Permute_jiekou(n, k); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }9. 没有重复数nums的全排列#include bits/stdc.h using namespace std; // 递归实现函数 void PermuteAll_Implement(vectorint nums, vectorint cur, vectorbool used, vectorvectorint result) { // 当前路径长度等于数组长度时加入结果 if (cur.size() nums.size()) { result.push_back(cur); return; } // 遍历候选数字 for (int i 0; i nums.size(); i) { // 剪枝如果当前数字已被使用则跳过 if (used[i]) continue; // 处理选择当前数字 cur.push_back(nums[i]); used[i] true; // 递归 PermuteAll_Implement(nums, cur, used, result); // 回溯撤销选择 cur.pop_back(); used[i] false; } } // 接口函数 vectorvectorint PermuteAll_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; vectorbool used(nums.size(), false); PermuteAll_Implement(nums, cur, used, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result PermuteAll_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }10. 带重复数nums的全排列#include bits/stdc.h using namespace std; // 递归实现函数 void PermuteUnique_Implement(vectorint nums, vectorint cur, vectorbool used, vectorvectorint result) { // 当前路径长度等于数组长度时加入结果 if (cur.size() nums.size()) { result.push_back(cur); return; } // 遍历候选数字 for (int i 0; i nums.size(); i) { // 剪枝1如果当前数字已被使用则跳过 if (used[i]) continue; // 剪枝2同层去重排序后当前数字与前一个数字相同且前一个未使用时跳过当前 // 保证相同数字在排列中的相对顺序避免生成重复排列 if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; // 处理选择当前数字 cur.push_back(nums[i]); used[i] true; // 递归 PermuteUnique_Implement(nums, cur, used, result); // 回溯撤销选择 cur.pop_back(); used[i] false; } } // 接口函数 vectorvectorint PermuteUnique_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; vectorbool used(nums.size(), false); // 排序是去重的前提 sort(nums.begin(), nums.end()); PermuteUnique_Implement(nums, cur, used, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result PermuteUnique_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }11.n皇后12.解数独37. 解数独 | 回溯法 | 二维递归 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源
CCF-CSP回溯算法
回溯算法主要是三个题型组合子集排序大致框架都是 确定递归函数的参数递归终止条件单层递归逻辑回溯算法用于解决for循环多的问题本质就是递归本文所使用的代码风格都是完整输入输出函数调用接口和具体实现用两个函数表达就这么几种题型理解之后会发现还是很简单的就像填空题一样无非是怎么处理重复问题题目要什么1. 1-n中k个的组合给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int n, int k, int startIndex, vectorint cur, vectorvectorint res) { if (cur.size() k) { res.push_back(cur); return; } for (int i startIndex; i n - (k - cur.size()) 1; i) { cur.push_back(i); Combine_Implement(n, k, i 1, cur, res); cur.pop_back(); } } // 接口函数 vectorvectorint Combine_jiekou(int n, int k) { vectorvectorint res; vectorint cur; Combine_Implement(n, k, 1, cur, res); return res; } int main() { int n, k; cin n k; vectorvectorint result Combine_jiekou(n, k); for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }剪枝2.组合的和#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int targetSum, int k, int sum, int startIndex, vectorint cur, vectorvectorint result) { if (sum targetSum) { // 剪枝操作 return; } if (cur.size() k) { if (sum targetSum) result.push_back(cur); return; // 如果cur.size() k 但sum ! targetSum 直接返回 } for (int i startIndex; i 9 - (k - cur.size()) 1; i) { // 剪枝 sum i; // 处理 cur.push_back(i); // 处理 Combine_Implement(targetSum, k, sum, i 1, cur, result); // 注意i1调整startIndex sum - i; // 回溯 cur.pop_back(); // 回溯 } } // 接口函数 vectorvectorint Combine_jiekou(int k, int n) { vectorvectorint result; vectorint cur; Combine_Implement(n, k, 0, 1, cur, result); return result; } int main() { int k, n; cin k n; vectorvectorint result Combine_jiekou(k, n); for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }3.组合的和II#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int target, int startIndex, int sum, vectorint candidates, vectorint cur, vectorvectorint result) { // 剪枝和超过目标值直接返回 if (sum target) { return; } // 找到一组有效组合 if (sum target) { result.push_back(cur); return; } // 遍历候选数字 for (int i startIndex; i candidates.size(); i) { // 剪枝当前数字加上后若超过目标则后续数字更大直接结束循环需提前排序 if (sum candidates[i] target) break; sum candidates[i]; // 处理 cur.push_back(candidates[i]); // 处理 // 关键允许重复选取递归时 startIndex 传 i不是 i 1 Combine_Implement(target, i, sum, candidates, cur, result); sum - candidates[i]; // 回溯 cur.pop_back(); // 回溯 } } // 接口函数 vectorvectorint Combine_jiekou(vectorint candidates, int target) { vectorvectorint result; vectorint cur; // 排序是剪枝的前提 sort(candidates.begin(), candidates.end()); Combine_Implement(target, 0, 0, candidates, cur, result); return result; } int main() { vectorint candidates; int target; // 示例输入模拟先读入数组长度再读入数组元素和目标值 int n; cin n; for (int i 0; i n; i) { int x; cin x; candidates.push_back(x); } cin target; vectorvectorint result Combine_jiekou(candidates, target); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }4.组合的和III#include bits/stdc.h using namespace std; // 递归实现函数 void Combine_Implement(int target, int startIndex, int sum, vectorint candidates, vectorint cur, vectorvectorint result) { // 找到一组有效组合 if (sum target) { result.push_back(cur); return; } // 剪枝和超过目标值直接返回 if (sum target) { return; } // 遍历候选数字 for (int i startIndex; i candidates.size(); i) { // 剪枝当前数字加上后若超过目标则后续数字更大直接结束循环依赖排序 if (sum candidates[i] target) break; // 同层去重排序后同一层递归中遇到相同的数字只取第一个避免重复组合 if (i startIndex candidates[i] candidates[i - 1]) continue; sum candidates[i]; // 处理 cur.push_back(candidates[i]); // 处理 // 关键每个数字只能使用一次递归时 startIndex 传 i 1 Combine_Implement(target, i 1, sum, candidates, cur, result); sum - candidates[i]; // 回溯 cur.pop_back(); // 回溯 } } // 接口函数 vectorvectorint Combine_jiekou(vectorint candidates, int target) { vectorvectorint result; vectorint cur; // 排序是剪枝和去重的前提 sort(candidates.begin(), candidates.end()); Combine_Implement(target, 0, 0, candidates, cur, result); return result; } int main() { vectorint candidates; int target; // 示例输入模拟先读入数组长度再读入数组元素和目标值 int n; cin n; for (int i 0; i n; i) { int x; cin x; candidates.push_back(x); } cin target; vectorvectorint result Combine_jiekou(candidates, target); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }5.子集#include bits/stdc.h using namespace std; // 递归实现函数 void Subsets_Implement(int startIndex, vectorint nums, vectorint cur, vectorvectorint result) { // 无目标和个数限制每次进入递归都将当前路径加入结果空集和所有中间状态均包含 result.push_back(cur); // 终止条件当起始索引越界时结束也可在for循环条件中自然结束 if (startIndex nums.size()) { return; } // 遍历候选数字 for (int i startIndex; i nums.size(); i) { // 处理选择当前数字 cur.push_back(nums[i]); // 递归注意 startIndex 传 i 1保证每个元素只选一次且顺序向后 Subsets_Implement(i 1, nums, cur, result); // 回溯撤销选择不选当前数字尝试同层的下一个数字 cur.pop_back(); } } // 接口函数 vectorvectorint Subsets_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; Subsets_Implement(0, nums, cur, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result Subsets_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }6.子集II#include bits/stdc.h using namespace std; // 递归实现函数 void Subsets_Implement(int startIndex, vectorint nums, vectorint cur, vectorvectorint result) { // 每次进入递归都将当前路径加入结果空集和所有中间状态均包含 result.push_back(cur); // 终止条件起始索引越界时结束 if (startIndex nums.size()) { return; } // 遍历候选数字 for (int i startIndex; i nums.size(); i) { // 同层去重排序后同一层递归中遇到相同的数字只取第一个避免重复子集 if (i startIndex nums[i] nums[i - 1]) continue; // 处理选择当前数字 cur.push_back(nums[i]); // 递归startIndex 传 i 1保证每个元素只选一次且顺序向后 Subsets_Implement(i 1, nums, cur, result); // 回溯撤销选择 cur.pop_back(); } } // 接口函数 vectorvectorint Subsets_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; // 排序是去重的前提 sort(nums.begin(), nums.end()); Subsets_Implement(0, nums, cur, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result Subsets_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }7.递增子集#include bits/stdc.h using namespace std; // 递归实现函数 void FindSubsequences_Implement(int startIndex, vectorint nums, vectorint cur, vectorvectorint result) { // 当前路径长度至少为2时加入结果 if (cur.size() 2) { result.push_back(cur); } // 终止条件起始索引越界时结束 if (startIndex nums.size()) { return; } // 用于同层去重注意不能排序需用哈希集合记录本层已使用的数字 unordered_setint used; // 遍历候选数字 for (int i startIndex; i nums.size(); i) { // 剪枝若当前数字小于路径末尾数字则无法构成递增序列 if (!cur.empty() nums[i] cur.back()) continue; // 同层去重本层已经使用过相同数字则跳过 if (used.find(nums[i]) ! used.end()) continue; used.insert(nums[i]); // 处理选择当前数字 cur.push_back(nums[i]); // 递归startIndex 传 i 1保证每个元素只选一次且顺序向后 FindSubsequences_Implement(i 1, nums, cur, result); // 回溯撤销选择 cur.pop_back(); } } // 接口函数 vectorvectorint FindSubsequences_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; // 注意不能排序因为题目要求保持原数组顺序的递增子序列 FindSubsequences_Implement(0, nums, cur, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result FindSubsequences_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }8.1-n中k个的全排序#include bits/stdc.h using namespace std; // 递归实现函数 void Permute_Implement(int k, vectorint cur, vectorbool used, vectorvectorint result) { // 当前路径长度达到k时加入结果 if (cur.size() k) { result.push_back(cur); return; } // 遍历候选数字1到n for (int i 1; i n; i) { // 剪枝如果当前数字已被使用则跳过 if (used[i]) continue; // 处理选择当前数字 cur.push_back(i); used[i] true; // 递归 Permute_Implement(k, cur, used, result); // 回溯撤销选择 cur.pop_back(); used[i] false; } } // 接口函数 vectorvectorint Permute_jiekou(int n, int k) { vectorvectorint result; vectorint cur; vectorbool used(n 1, false); Permute_Implement(k, cur, used, result); return result; } int main() { int n, k; // 读入n和k cin n k; vectorvectorint result Permute_jiekou(n, k); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }9. 没有重复数nums的全排列#include bits/stdc.h using namespace std; // 递归实现函数 void PermuteAll_Implement(vectorint nums, vectorint cur, vectorbool used, vectorvectorint result) { // 当前路径长度等于数组长度时加入结果 if (cur.size() nums.size()) { result.push_back(cur); return; } // 遍历候选数字 for (int i 0; i nums.size(); i) { // 剪枝如果当前数字已被使用则跳过 if (used[i]) continue; // 处理选择当前数字 cur.push_back(nums[i]); used[i] true; // 递归 PermuteAll_Implement(nums, cur, used, result); // 回溯撤销选择 cur.pop_back(); used[i] false; } } // 接口函数 vectorvectorint PermuteAll_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; vectorbool used(nums.size(), false); PermuteAll_Implement(nums, cur, used, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result PermuteAll_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }10. 带重复数nums的全排列#include bits/stdc.h using namespace std; // 递归实现函数 void PermuteUnique_Implement(vectorint nums, vectorint cur, vectorbool used, vectorvectorint result) { // 当前路径长度等于数组长度时加入结果 if (cur.size() nums.size()) { result.push_back(cur); return; } // 遍历候选数字 for (int i 0; i nums.size(); i) { // 剪枝1如果当前数字已被使用则跳过 if (used[i]) continue; // 剪枝2同层去重排序后当前数字与前一个数字相同且前一个未使用时跳过当前 // 保证相同数字在排列中的相对顺序避免生成重复排列 if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; // 处理选择当前数字 cur.push_back(nums[i]); used[i] true; // 递归 PermuteUnique_Implement(nums, cur, used, result); // 回溯撤销选择 cur.pop_back(); used[i] false; } } // 接口函数 vectorvectorint PermuteUnique_jiekou(vectorint nums) { vectorvectorint result; vectorint cur; vectorbool used(nums.size(), false); // 排序是去重的前提 sort(nums.begin(), nums.end()); PermuteUnique_Implement(nums, cur, used, result); return result; } int main() { vectorint nums; int n; // 读入数组长度及元素 cin n; for (int i 0; i n; i) { int x; cin x; nums.push_back(x); } vectorvectorint result PermuteUnique_jiekou(nums); // 输出结果 for (int i 0; i result.size(); i) { for (int j 0; j result[i].size(); j) { cout result[i][j] ; } cout endl; } return 0; }11.n皇后12.解数独37. 解数独 | 回溯法 | 二维递归 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源
