0.回溯算法介绍 

什么是回溯算法
回溯算法是⼀种经典的递归算法，通常⽤于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从⼀个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态⽆法前进时，回退到前⼀个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护⼀个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核⼼思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索；否则，回退到上⼀个状态，重新做出选择。回溯算法通常⽤于解决具有多个解，且每个解都需要搜索才能找到的问题。
 

1.全排列

全排列

思路历程： 

 

 

class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7];vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(check[i] == false){path.push_back(nums[i]);check[i] = true;dfs(nums);path.pop_back();check[i] = false;}}}
};

2.子集 

子集

 思路历程

 

解法一代码： 

class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}//选path.push_back(nums[pos]);dfs(nums, pos + 1);path.pop_back();//恢复现场//不选dfs(nums, pos + 1);}
};

解法二代码： 

class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){ret.push_back(path);for(int i = pos; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back(); //恢复现场}}
};