深搜、暴搜、回溯、剪枝（C++）1
一、全排列
1、题目描述
2、代码
class Solution
{
public:
// 全局变量
vector<vector<int>> ret;
vector<int> path;
bool check[7]; // 该题目最大到6--用以判断每个字符的使用情况
vector<vector<int>> permute(vector<int>& nums)
{
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
// 递归出口
if(nums.size() == path.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;
}
}
}
};
3、解析
二、子集
1、题目描述
2、代码
代码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)
{
// 1、递归出口
if(pos == nums.size())
{
ret.push_back(path);
return;
}
// 2、选
path.push_back(nums[pos]);
dfs(nums, pos + 1); // 递归到下一层
path.pop_back(); // 恢复现场
// 3、不选
dfs(nums, pos + 1);
}
};
代码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)
{
// 1、递归出口
ret.push_back(path);
// 2、递归
for (int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back(); // 恢复现场
}
}
};
3、解析
三、找出所有子集的异或总和再求和
1、题目描述
2、代码
class Solution
{
public:
// 1、全局变量
int sum = 0; // 记录最终结果
int path = 0; // 记录当前异或后的值
int subsetXORSum(vector<int>& nums)
{
dfs(nums, 0);
return sum;
}
// 2、递归
void dfs(vector<int>& nums, int pos)
{
// 1、递归出口
sum += path;
// 2、往下递归
for(int i = pos; i < nums.size(); i++)
{
path ^= nums[i];
dfs(nums, i + 1);
path ^= nums[i];
}
}
};
3、解析
四、全排列II
1、题目解析
2、代码
代码1：
class Solution
{
public:
// 1、全局变量
vector<vector<int>> ret; // 记录返回的数组
vector<int> path; // 记录路径
bool check[9]; // 判断是否被使用过
vector<vector<int>> permuteUnique(vector<int>& nums)
{
// 2、排序
sort(nums.begin(), nums.end());
// 3、进行递归
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
// 1、递归出口
if(pos == nums.size())
{
ret.push_back(path);
return;
}
// 2、每一层的循环
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进行增加
path.push_back(nums[i]);
check[i] = true;
// 递归
dfs(nums, pos + 1);
// 回溯 -- 恢复现场
path.pop_back();
check[i] = false;
}
}
};
代码2：
class Solution
{
public:
// 1、全局变量
vector<vector<int>> ret; // 记录返回的数组
vector<int> path; // 记录路径
bool check[9]; // 判断是否被使用过
vector<vector<int>> permuteUnique(vector<int>& nums)
{
// 2、排序
sort(nums.begin(), nums.end());
// 3、进行递归
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
// 1、递归出口
if(pos == nums.size())
{
ret.push_back(path);
return;
}
// 2、每一层的循环
for(int i = 0; i < nums.size(); i++)
{
// 不合法情况进行剪枝
if(check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true))
{
// path进行增加
path.push_back(nums[i]);
check[i] = true;
// 递归
dfs(nums, pos + 1);
// 回溯 -- 恢复现场
path.pop_back();
check[i] = false;
}
}
}
};
3、解析
五、电话号码的字母组合
1、题目描述
2、代码
class Solution
{
public:
// 全局变量
string hash[10] = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string path; // 记录路径
vector<string> ret; // 返回的组合
vector<string> letterCombinations(string digits)
{
if(digits.size() == 0)
return ret;
dfs(digits, 0);
return ret;
}
void dfs(string& digits, int pos)
{
// 递归出口
if(digits.size() == pos)
{
ret.push_back(path);
return;
}
// 循环找对应关系
for(auto ch : hash[digits[pos] - '0']) // 掏出来字符串进行遍历当前下标所对应的字符串
{
// 尾插进去
path.push_back(ch);
dfs(digits, pos + 1);
path.pop_back(); // 恢复现场
}
}
};
3、解析
