全排列:
* 给一个数组nums,返回所有的全排列,按每个位置枚举,不包括空集,延伸题型会限制重复解
子集:
* 给一个数组nums,返回所有的子集,按元素选或者不选枚举,可以是空集,延伸题型会限制重复解
如何去重:(首先要排序)
if (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false)
continue;
是否需要bool flag[]:如果不查重不排序,那么最好需要用来做位置的判断
其实在力扣题解里大部分都没有用y总模板的第u位置,因为acw需要在u位置更新元素,而力扣题直接push_back到path里
关于是否需要恢复现场:
https://blog.csdn.net/weixin_45221477/article/details/105058803
总结就是如果答案是n个位置都要写满,那就需要,如果答案存在空集或不用写满,就不需要
力扣46 全排列
https://leetcode.cn/problems/permutations/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> permute(vector<int>& nums)
{
vector<bool> flag(nums.size(), false);
dfs(nums, 0, flag);
return res;
}
void dfs(const vector<int>& nums, int u, vector<bool>& flag)
{
if (u == nums.size()) // 因为是按位置枚举,所以u这里写path.size()也是一样
{
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (!flag[i]) // 写成if(flag[i]) continue;也可以
{
path.push_back(nums[i]);
flag[i] = true;
dfs(nums, u + 1, flag);
path.pop_back();
flag[i] = false; // 恢复现场,因为该题不查重所以一定要有
}
}
}
};
力扣47 全排列2
https://leetcode.cn/problems/permutations-ii/
代码就是多了个排序+查重
acw打卡: https://www.acwing.com/activity/content/code/content/3374018/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> permuteUnique(vector<int>& nums)
{
vector<bool> flag(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重一定要排序!!!
dfs(nums, 0, flag);
return res;
}
void dfs(const vector<int>& nums, int u, vector<bool>& flag)
{
if (u == nums.size())
{
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false) // 注意最后的判断
continue;
if (flag[i])
continue;
path.push_back(nums[i]);
flag[i] = true;
dfs(nums, u + 1, flag);
path.pop_back();
flag[i] = false; // 恢复现场,和子集的区别在这里
}
}
};
力扣78 子集
https://leetcode.cn/problems/subsets/
使用的是y总方法:对每个位置枚举,同时选择是否放置元素
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums)
{
vector<bool> flag(nums.size(), false);
dfs(nums, 0, flag);
return res;
}
void dfs(const vector<int>& nums, int u, vector<bool>& flag)
{
if (u == nums.size()) // 这里就不能写path.size()了,因为不是每个位置都有元素的,要看第u位置
{
res.push_back(path);
return;
}
// 不选当前位置
flag[u] = false; // 这个是必要的,因为不确定上一层的flag状态
dfs(nums, u + 1, flag);
// 选择当前位置
for (int i = u; i < nums.size(); i++) // 从当前位向后枚举,可以避免出现123 321的解
{
if (!flag[i])
{
flag[i] = true;
path.push_back(nums[i]);
dfs(nums, i + 1, flag);
path.pop_back();
// 没有flag[i] = false; 因为不需要恢复现场,否则会出现12' ',1''2,''12的重复解了
}
}
}
};
力扣90 子集2
https://leetcode.cn/problems/subsets-ii/
其实我这种写法不好
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
vector<bool> flag(nums.size(), false);
sort(nums.begin(), nums.end()); // 需要排序
dfs(nums, 0, flag);
return res;
}
void dfs(const vector<int>& nums, int u, vector<bool>& flag)
{
if (u == nums.size())
{
res.push_back(path);
return;
}
// 不选:
flag[u] = false;
dfs(nums, u + 1, flag);
// 选
for (int i = u; i < nums.size(); i++)
{
// 注意去重条件,i>0不能写i>u,这里我还需要再思考一下
// 最重要的是第一次出现的重复,即1122的11,而后面的都会被nums[i]==nums[i - 1]干掉
if (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false)
continue;
if (!flag[i])
{
flag[i] = true;
path.push_back(nums[i]);
dfs(nums, i + 1, flag);
path.pop_back();
}
}
}
};
acw上面相关DFS递归数组的题解:
92 递归实现指数型枚举
https://www.acwing.com/activity/content/code/content/2567855/
93 递归实现组合型枚举
https://www.acwing.com/activity/content/code/content/2588120/
94 递归实现排列型枚举
https://www.acwing.com/activity/content/code/content/2567978/