当前位置:网站首页>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;
}
边栏推荐
- C control refresh
- Basic use of ActiveMQ in Message Oriented Middleware
- Technology blog | how to communicate using SSE
- Home environment monitoring system design (PC version) (mobile app version to be determined)
- Fairmot yolov5s to onnx
- C#入门教程
- ts环境搭建
- Leetcode daily question - 515 Find the maximum value in each tree row
- [single chip microcomputer project training] multipoint temperature wireless acquisition system based on nRF905
- Modular programming of digital light intensity sensor module gy-30 (main chip bh1750fvi) controlled by single chip microcomputer (under continuous updating)
猜你喜欢
Leetcode daily question - 515 Find the maximum value in each tree row
How to use printf of 51 single chip microcomputer
Keil and Proteus joint commissioning
PCB board design - automatic layout 2021-10-15
How to use ad wiring for PCB design?
基于STM32MP157调试MIPI-DSI屏幕
Find out what informatization is, and let enterprises embark on the right path of transformation and upgrading
What if there is no point in data visualization?
Tips on how to design soft and hard composite boards ~ 22021/11/22
(tool class) use SecureCRT as the communication medium
随机推荐
【日常训练】207. 课程表
Can I open a stock account with a compass? Is it safe?
Static bit rate (CBR) and dynamic bit rate (VBR)
Summary of small problems in smartbugs installation
海思3559 sample解析:vio
音频(五)音频特征提取
國外LEAD域名郵箱獲取途徑
微信小程序入门记录
php入门基础记录
(tool class) quickly add time to code in source insight
Modular programming of wireless transmission module nRF905 controlled by single chip microcomputer
Storage of Galileo broadcast ephemeris in rtklib-b33
点云智绘在智慧工地中的应用
一“石”二“鸟”,PCA有效改善机载LiDAR林下地面点部分缺失的困局
El input to add words to the tail
C#获取exe的版本号-文件版本and程序集版本
Cglib dynamic proxy
Six causes of PCB disconnection 2021-10-20
Hisilicon 3559 sample parsing: Vio
Atlassian confluence漏洞分析合集