穷举vs暴搜vs深搜vs回溯vs剪枝（一）

全排列

题目：全排列

思路

通过深度优先搜索的方式，不断枚举每个数在当前位置的可能性，然后回溯到上一个状态，直到枚举完所有可能性得到正确的结果

• res：一个二维向量vector<vector<int>>，用于存储所有生成的排列。
• path：一个一维向量vector<int>，用于存储当前正在构建的排列。
• check：一个布尔数组bool check[7]，用于标记数组nums中的每个元素是否已经被用于当前排列中。这里假设nums数组的大小不会超过6（因为数组索引从0开始，最大索引为6时，数组大小为7）。
• 递归的终止条件是path的大小等于nums的大小。
• 在递归过程中，使用check数组来确保不会重复使用同一个元素。
• 使用path.push_back(nums[i])和path.pop_back()来实现回溯，即在尝试下一个元素之前，需要将当前元素从path中移除，以便尝试其他可能的元素组合。
• 通过check[i] = true和check[i] = false来标记元素是否已被使用。

C++代码

class Solution 
{vector<vector<int>> res;vector<int> path;bool check[7];public:void dfs(vector<int>& nums){if(nums.size() == path.size()){res.push_back(path);return ;}for(int i = 0; i < nums.size(); i ++ ){if(!check[i]){path.push_back(nums[i]);check[i] = true;dfs(nums);// 回溯 -> 恢复现场path.pop_back();check[i] = false;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return res;}
};

子集

题目：子集

思路1

我们先将所有结果个数为1的选出来，再再其基础上选出结果个数为2的，依次类推

• 从 pos 开始遍历 nums 数组。对于每个位置 i ，执行以下操作：
  将 nums[i] 添加到 path 中。
• 递归调用 dfs 函数，以 i + 1 作为新的起始位置，继续搜索。
• 在递归调用返回后，进行回溯操作：将刚刚添加到 path 中的 nums[i] 移除，以便尝试其他可能的元素组合（或停止进一步搜索）。

C++代码

class Solution 
{vector<vector<int>> ret;vector<int> path;
public: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();}}
};

思路2

依次枚举，1选不选，选的话在1基础上2选不选，选的话在2基础上选不选，枚举出所有结果；当当前位置等于数组大小时，将结果加入答案中

• 首先检查pos是否等于nums的大小。如果是，说明已经遍历到数组的末尾，此时path代表了一个完整的子集（可能是空集，也可能是包含数组所有元素的集合，这取决于dfs的调用过程）。然后，将这个子集添加到ret中，并返回
• 将nums[pos]添加到path中，然后递归调用dfs函数，以pos + 1作为新的起始位置继续搜索。在递归调用返回后，执行回溯操作：从path中移除nums[pos]，以便尝试其他可能的元素组合或停止进一步搜索。

class Solution 
{vector<vector<int>> ret;vector<int> path;
public: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);}
};

找出所有子集的异或总和再求和

题目：找出所有子集的异或总和再求和

思路

本题和上题思路一样，我们使用上题的第一种思路，依次枚举，1选不选，选的话在1基础上2选不选，选的话在2基础上选不选；
不同的是将每个子集的值异或，并将其相加

• 从数组的第一个元素开始，递归地构建所有可能的子集
• 在每个递归步骤中，可以选择包含当前元素（通过异或操作更新path）或不包含当前元素（直接递归到下一个位置）
• int path选择1将其异或在path上，再选2异或在path上；
• 当到达数组的末尾时，将当前的 path（即当前子集的异或和）加到 res 上

C++代码

class Solution 
{int path;int res;
public:void dfs(vector<int>& nums, int pos){res += path;for(int i = pos; i < nums.size(); i ++ ){path ^= nums[i];dfs(nums, i + 1);path ^= nums[i];}}int subsetXORSum(vector<int>& nums) {dfs(nums, 0);return res;}
};

全排列 II

题目：全排列 II

思路

同一个节点的分支中，相同的元素只能选择一次
同一个数只能使用一次

---

• 只关心不合法分支

if(cheak[i] == true) || (i != 0 && nums[i] == nums[i-1] && cheak[i-1] == false))

C++代码

class Solution 
{vector<int> path;vector<vector<int>> ret; bool check[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(check[i] == true|| (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false)) continue;path.push_back(nums[i]);check[i] = true;dfs(nums, pos + 1);path.pop_back();check[i] = false;}}
};

• 只关心合法分支

if(cheak[i] == false) && (i == 0 || nums[i] != nums[i-1] ||cheak[i-1] != false))

C++代码

class Solution 
{vector<int> path;vector<vector<int>> ret; bool check[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] != false)) {path.push_back(nums[i]);check[i] = true;dfs(nums, pos + 1);path.pop_back();check[i] = false;}}}
};

电话号码的字母组合

题目：电话号码的字母组合

思路

利用一个全局的字符串数组来帮我映射数组和字母之间的关系

• 如果pos等于digits的长度，说明已经处理完所有数字，将当前的path（即一个完整的字母组合）添加到结果数组ret中，并返回
• 否则，对于当前数字digits[pos]，遍历其对应的所有字母（通过str[digits[pos] - '0']访问。对于每个字母，执行以下操作
• • 将当前字母添加到path的末尾。
• • 递归调用dfs函数，处理下一个数字pos + 1。
• • 在递归返回后，将刚刚添加的字母从path中移除，以便尝试当前数字对应的下一个字母。

C++代码

class Solution 
{vector<string> ret;string path;string str[10]={"","", "abc", "def","ghi", "jkl", "mno","pqrs", "tuv", "wxyz"};
public:vector<string> letterCombinations(string digits) {if(digits.size() == 0) return ret;dfs(digits, 0);return ret;}void dfs(string& digits, int pos){if(pos == digits.size()){ret.push_back(path);return;}for(auto ch : str[digits[pos] - '0']){path.push_back(ch);dfs(digits, pos + 1);path.pop_back();}}
};