当前位置:网站首页>Buckle 78: subset
Buckle 78: subset
2022-06-25 07:50:00 【Yingtai night snow】
Power button 78: A subset of
Title Description
Give you an array of integers nums
, Elements in an array Different from each other . Returns all possible subsets of the array ( Power set ).
Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .
I / O example
Input :nums = [1,2,3]
Output :[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Input :nums = [0]
Output :[[],[0]]
Algorithm one , Use a dictionary for backtracking
vector<vector<int>>subsets(vector<int>&nums)
{
// Set judgment array
vector<bool>vaild(nums.size(),false);
// Set save array
vector<vector<int>>res;
// Set the traversal depth
int depth=0;
// Length of array
int length=nums.size();
getSubsets(nums,length,depth,vaild,res);
return res;
}
// Establish functions to realize the function of iteration , according to vaild The change of function value is realized
void getSubsets(vector<int>nums,int length,int depth,vector<bool>&vaild,vector<vector<int>>&res)
{
vector<int>path;
if(depth==length)
{
for(int i=0;i<length;i++)
{
if(vaild[i]==true)
{
path.push_back(nums[i]);
}
}
res.push_back(path);
}
else{
// Change the current vaild Two fractions of value true and false, Keep exploring
vaild[depth]=true;
getSubsets(nums,length,depth+1,vaild,res);
vaild[depth]=false;
getSubsets(nums,length,depth+1,vaild,res);
}
}
Algorithm 2 , Using backtracking
// Use the idea of iteration
vector<vector<int>>subsets2(vector<int>&nums)
{
vector<vector<int>>res;
vector<int>path;
int start=0;
backTrack(nums,path,start,res);
return res;
}
void backTrack(vector<int>nums,vector<int>&path,int start,vector<vector<int>>&res)
{
res.push_back(path);
for(int i=start;i<nums.size();i++)
{
path.push_back(nums[i]);
backTrack(nums,path,i+1,res);
path.pop_back();
}
}
Algorithm 3: Use dynamic programming
// Using the idea of dynamic programming
vector<vector<int>>subsets3(vector<int>&nums)
{
vector<vector<int>>res;
vector<int>path;
// Add an empty set to the array first
res.push_back(path);
for(int i=0;i<nums.size();i++)
{
int size=res.size();
// Add... To the previous subset
for(int j=0;j<size;j++)
{
vector<int>newList=res[j];
newList.push_back(nums[i]);
res.push_back(newList);
}
}
return res;
}
边栏推荐
猜你喜欢
【蒸馏】PointDistiller: Structured Knowledge DistillationTowards Efficient and Compact 3D Detection
OAuth 2.0一键登录那些事
无“米”,也能煮“饭”利用“点云智绘”反演机载LiDAR林下缺失地面点攻略
How to use ad wiring for PCB design?
Modular programming of digital light intensity sensor module gy-30 (main chip bh1750fvi) controlled by single chip microcomputer (under continuous updating)
Six causes of PCB disconnection 2021-10-20
VectorDraw Web Library 10.10
Invalid Navicat scheduled task
函数模板_类模板
一文了解 | 革兰氏阳性和阴性菌区别,致病差异,针对用药
随机推荐
Basic use of ActiveMQ in Message Oriented Middleware
Do you know why the PCB produces tin beads? 2021-09-30
一“石”二“鸟”,PCA有效改善机载LiDAR林下地面点部分缺失的困局
VectorDraw Web Library 10.10
Storage of Galileo broadcast ephemeris in rtklib-b33
FairMOT yolov5s转onnx
Modular programming of oled12864 display controlled by single chip microcomputer
消息中间件之ActiveMQ的基本使用
【QT】Qt 5 的程序:打印文档
无“米”,也能煮“饭”利用“点云智绘”反演机载LiDAR林下缺失地面点攻略
【蒸馏】PointDistiller: Structured Knowledge DistillationTowards Efficient and Compact 3D Detection
单位转换-毫米转像素-像素转毫米
C control refresh
一文了解 | 革兰氏阳性和阴性菌区别,致病差异,针对用药
opencv最小值滤波(不局限于图像)
Modular programming of LCD1602 LCD controlled by single chip microcomputer
Cglib dynamic proxy
Audio (V) audio feature extraction
php入门基础记录
海思3559 sample解析:vio