子集、全排列、组合 问题模式
78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
输入: nums = [1,2,3]
输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
子集： 对每个元素都有 取与不取 两个状态，所以共有2^n种子集，正好可以使用对应位的二进制掩码来判断每个元素的状态，1取0不取，共有1<<n种状态
拿题目来举例子：
对应二进制数字为：000 001 010 011 100 101 110 111
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int len = nums.size();
if(len<1) return vector<vector<int>> {{}};
int bit_map = 0;
int end = 1<<len; // 2^n class
vector<vector<int>> res;
vector<int> tmp;
// 2^n个掩码(状态)，然后取当前掩码对应的子集，需要遍历数组 n*2^n
while(bit_map<end){
for(int i=0;i<len;i++)
if((1<<i)&bit_map) tmp.push_back(nums[i]);
res.push_back(tmp);
tmp.clear();
bit_map++;
}
return res;
}
};
复杂度分析
时间复杂度：O(N×2^N)，生成所有的子集，并复制到输出列表中。
空间复杂度：O(2^N)，存储所有子集,共N个元素，每个元素都有可能存在或者不存在。
递归回溯 求解
其实存在两种递归求解的方法，一种是把解空间当做二叉树进行深度优先或者广度优先的遍历，一种则是把解空间当做图(多叉树)进行深度优先的遍历。
- 当成一个满二叉树 求解, 对于每一个 元素 都有 选与不选 两个结果，对应左右节点，这样每个叶子节点都是一个结果，但是这样处理会 遍历所有节点，速度会稍慢。
class Solution {
public:
vector<vector<int>> res;
void dfs(const vector<int>& nums,int index,vector<int>& ans){
if(index == nums.size()) res.push_back(ans);
if(index < nums.size()){
dfs(nums,index+1,ans); // 不选
ans.push_back(nums[index]);
dfs(nums,index+1,ans); // 选
ans.pop_back(); // 删除 回溯到上一个状态
}
}
vector<vector<int>> subsets(vector<int>& nums) {
if(nums.size()<1) return vector<vector<int>> {{}};
vector<int> ans;
dfs(nums,0,ans);
return res;
}
};
// [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
深度搜索，一直不选择到底，然后回溯慢慢添加元素，
- 回溯
它的每一个结点是满足题目要求的一个解，结点之间的相邻关系取决于该结点是否还可以塞入其他元素。
class Solution {
public:
vector<vector<int>> res;
void backtrack(const vector<int> nums,int index,vector<int>& tmp){
res.push_back(tmp);
for(int i=index;i<nums.size();i++){
tmp.push_back(nums[i]);
backtrack(nums,i+1,tmp);
tmp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
if(!nums.size()) return res;
vector<int> tmp;
backtrack(nums,0,tmp);
return res;
}
};
递归回溯可能模板
void dfs(待搜索集合,递归层数，状态变量1,2,结果集){
// 终止条件 return
// 或者 达到搜索结果 return
for(可执行分支){
// 剪枝
if 递归到第几层, 状态变量 1, 状态变量 2, 符合一定的剪枝条件:
continue
// do something 对状态变量的操作
dfs(待搜索集合,递归层数+1，状态变量1,2,结果集); // 继续递归
// do something 回溯 对状态变量的操作
// 如 push_back(i) pop_back() 删除这个元素，回溯到添加这个元素上一步
}
}
90 子集II
回溯
去重，首先对数组进行排序，使重复元素挨在一起
然后回溯时，如果同一层分支中存在重复元素，则跳过
class Solution {
public:
vector<vector<int>> res;
void backtrack(const vector<int> nums,int index,vector<int>& tmp){
res.push_back(tmp);
for(int i=index;i<nums.size();i++){
//同层递归中，第二次遇到重复元素跳出
if(i != index && nums[i-1]==nums[i])
continue;
tmp.push_back(nums[i]);
backtrack(nums,i+1,tmp);
tmp.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
if(!nums.size()) return res;
vector<int> tmp;
sort(nums.begin(),nums.end());
backtrack(nums,0,tmp);
return res;
}
};
77 组合
回溯
- 使用多叉图的方法，对每个
class Solution {
public:
vector<vector<int>> res;
void backtrack(int n,int k,vector<int>& tmp,int index){
if(tmp.size() == k) res.push_back(tmp);
for(int i=index;i<=n;i++){
tmp.push_back(i);
backtrack(n,k,tmp,i+1);
tmp.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
if(k<1) return res;
vector<int> tmp;
backtrack(n,k,tmp,1);
return res;
}
};
二叉树 深搜
- 对每个节点，都有选择与不选择 两个状态，分别对应两个分支， 但是因为取到k个元素就满足，所以递归到k深度 即可返回
class Solution {
public:
vector<vector<int>> res;
void dfs(int n,int k,int index,vector<int>& tmp){
if(tmp.size() == k) {
res.push_back(tmp);
return ;
}
if(index<=n && tmp.size() < k){
dfs(n,k,index+1,tmp);
tmp.push_back(index);
dfs(n,k,index+1,tmp);
tmp.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
if(k<1) return vector<vector<int>> {{}};
vector<int> tmp;
dfs(n,k,1,tmp);
return res;
}
};
46 全排列
class Solution {
public:
vector<vector<int>> res;
void dfs(const vector<int> nums,vector<bool>& dp,vector<int>& tmp,int len){
if(tmp.size() == len) res.push_back(tmp);
for(int i=0;i<len;i++){
if(!dp[i]){
tmp.push_back(nums[i]);
dp[i] = true;
dfs(nums,dp,tmp,len);
tmp.pop_back();
dp[i] = false;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
int len = nums.size();
if(!len) return res;
vector<bool> dp(len,false);
vector<int> tmp;
dfs(nums,dp,tmp,len);
return res;
}
};
47 全排列II
class Solution {
public:
vector<vector<int>> res;
void dfs(const vector<int> nums,vector<bool>& dp,vector<int>& tmp,int len){
if(tmp.size() == len) res.push_back(tmp);
for(int i=0;i<len;i++){
if(i!=0 && nums[i-1]==nums[i] && !dp[i-1]) continue;
if(!dp[i]){
tmp.push_back(nums[i]);
dp[i] = true;
dfs(nums,dp,tmp,len);
tmp.pop_back();
dp[i] = false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
int len = nums.size();
if(!len) return res;
sort(nums.begin(),nums.end());
vector<bool> dp(len,false);
vector<int> tmp;
dfs(nums,dp,tmp,len);
return res;
}
};
39 组合总和
- 回溯算法
这一题的难点在于数字可以无限制重复，但是又要避免解集中出现重复,由此想到累加的下一次要从自身的index开始。
递归条件 加上当前元素 不超过目标值 则可以进一步递归 超过则退出
可以先排序，然后超过元素之后的所有元素都可以跳过 不排序的话，就对所有元素进行遍历，判断是否进入下一层递归
去重
如果不去重，会产生 [223] [232] [322] 这些类似结果
class Solution {
public:
vector<vector<int>> res;
void dfs(const vector<int> nums,int sum,int target,int len,vector<int>& tmp,int index){
if(sum == target) {
res.push_back(tmp);
return ;
}
for(int i=index;i<len;i++){
if(sum+nums[i]>target) continue;
tmp.push_back(nums[i]);
dfs(nums,sum+nums[i],target,len,tmp,i);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int len = candidates.size();
if(!len) return res;
vector<int> tmp;
dfs(candidates,0,target,len,tmp,0);
return res;
}
};
// sort(nums)
// if(sum+nums[i]>target) break;
// 排序后 如果当前元素大于目标值 则后面所有元素都大于 直接跳出循环
40 组合总和II
回溯
- 每个字符只能使用一次 所以将index当做状态变量递归
- 去重，首先对数组进行排序，重复的元素在一起，递归时 判断上次元素和这次元素相等则跳出，
- 剪枝 如果当前元素已经大于目标值，则跳出循环，此后所有元素不满足 目标状态
class Solution {
public:
vector<vector<int>> res;
void dfs(const vector<int>& nums,int target,int sum,int index,vector<int>& tmp){
if(sum == target) res.push_back(tmp);
for(int i=index;i<nums.size() && sum+nums[i]<=target;i++){
if(i!=index && nums[i-1]==nums[i]) continue;
tmp.push_back(nums[i]);
dfs(nums,target,sum+nums[i],i+1,tmp);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int len = candidates.size();
if(!len) return res;
sort(candidates.begin(),candidates.end());
vector<int> tmp;
dfs(candidates,target,0,0,tmp);
return res;
}
};
关于去重一个比较清晰的解释
其实就是如何 去除同层的重复 并且保留不同层的相同值
if(i!=index && nums[i-1]==nums[i]) continue;主要实现就是i!=index,重复元素在同层第二次取到时 一定满足i!=index所以将它去除
投递快手等公司10个岗位 >