[TOC] ## 背景 回溯法（backtrack）常用于遍历列表所有子集，是DFS深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际是一个决策树的遍历过程。时间复杂度一般O(n!)，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。 ## 模板 ``` result = [] func backtrack(选择列表,路径): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(选择列表,路径) 撤销选择 ``` ## 示例 #### [78\. 子集](https://leetcode-cn.com/problems/subsets/) 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 ``` class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; vector<int> subset; backtrack(nums, 0, subset, result); return result; } void backtrack(const vector<int>& nums, int pos, vector<int>& subset, vector<vector<int>>& result) { result.push_back(subset); for (int i = pos; i < nums.size(); i++) { subset.push_back(nums[i]); backtrack(nums, i + 1, subset, result); subset.pop_back(); } } }; ``` #### [90\. 子集 II](https://leetcode-cn.com/problems/subsets-ii/) 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集） ``` class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> result; vector<int> subset; sort(nums.begin(), nums.end()); // 先排序 backtrack(nums, 0, subset, result); return result; } void backtrack(const vector<int>& nums, int pos, vector<int>& subset, vector<vector<int>>& result) { result.push_back(subset); // 选择时需要剪枝、处理、撤销选择 for (int i = pos; i < nums.size(); i++) { if (i > pos && nums[i] == nums[i-1]) // 跳过相同层数的相同元素 continue; subset.push_back(nums[i]); backtrack(nums, i + 1, subset, result); subset.pop_back(); } } }; ``` #### [46\. 全排列](https://leetcode-cn.com/problems/permutations/) 给定一个 没有重复 数字的序列，返回其所有可能的全排列 ``` class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; vector<int> subset; vector<bool> visit(nums.size(), false); backtrack(nums, visit, subset, result); return result; } void backtrack(const vector<int>& nums, vector<bool>& visit, vector<int>& subset, vector<vector<int>>& result); { if (subset.size() == nums.size()) { result.push_bask(subset); return; } for (int i = 0; i < nums.size(); i++) { if (visit[i]) continue; subset.push_bask(nums[i]); visit[i] = true; backtrack(nums, visit, subset, result); subset.pop_back(); visit[i] = false; } } }; ``` #### [47\. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/) 给定一个可包含重复数字的序列，返回所有不重复的全排列 ``` class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> result; vector<bool> visit(nums.size(), false); vector<int> subset; sort(nums.begin(), nums.end()); // 先排序 backtrack(nums, visit, subset, result); return result; } void backtrack(const vector<int>& nums, vector<bool>& visit, vector<int>& subset, vector<vector<int>>& result) { if (subset.size() == nums.size()) { result.push_back(subset); return; } for (int i = 0; i < nums.size(); i++) { // 访问过 OR 上一个元素和当前相同，并且没有访问过 => 跳过 if (visit[i] || (i > 0 && !visit[i-1] && nums[i-1] == nums[i])) continue; visit[i] = true; subset.push_back(nums[i]); backtrack(nums, visit, subset, result); subset.pop_back(); visit[i] = false; } } }; ```