当前位置:网站首页>LeetCode 90. 子集 II
LeetCode 90. 子集 II
2022-07-02 06:07:00 【大白羊_Aries】
题目描述
解法
我们考虑回溯的方法,但是和 LeetCode 78. 子集 不同的是我们这里需要考虑剪枝的问题,例如对于题目例子 n u m s = [ 1 , 2 , 2 ] nums = [1,2,2] nums=[1,2,2],不剪枝的话生成的结果如下图所示
而正确的结果应该是
所以我们必须有剪枝这一步,体现在代码上,需要先进行排序,让相同的元素靠在一起,如果发现 n u m s [ i ] = = n u m s [ i − 1 ] nums[i] == nums[i-1] nums[i]==nums[i−1],则跳过。具体看下面实现
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> track;
backtrace(nums, 0, track);
return res;
}
void backtrace(vector<int>& nums, int start, vector<int> track)
{
res.push_back(track);
for (int i = start; i < nums.size(); i++)
{
if (i > start && nums[i] == nums[i - 1]) continue;
track.push_back(nums[i]);
backtrace(nums, i + 1, track);
track.pop_back();
}
}
};
边栏推荐
- Verifying downloaded files using sha256 files
- Software testing - concept
- External interrupts cannot be accessed. Just delete the code and restore it Record this unexpected bug
- TI毫米波雷达学习(一)
- STC8H8K系列汇编和C51实战——串口发送菜单界面选择不同功能
- 51单片机——ADC讲解(A/D转换、D/A转换)
- Google Play Academy 组队 PK 赛,正式开赛!
- On Web server
- Reading classic literature -- Suma++
- Talking about MySQL database
猜你喜欢
[C language] simple implementation of mine sweeping game
穀歌出海創業加速器報名倒計時 3 天,創業人闖關指南提前收藏!
Memcached installation
Summary of MySQL constraints
Happy Lantern Festival | Qiming cloud invites you to guess lantern riddles
Sumo tutorial Hello World
Stick to the big screen UI, finereport development diary
Mathematical statistics and machine learning
复杂 json数据 js前台解析 详细步骤《案例:一》
深度学习分类网络--VGGNet
随机推荐
Stc8h8k Series Assembly and c51 Real combat - NIXIE TUBE displays ADC, Key Series port reply Key number and ADC value
Summary of MySQL constraints
来自读者们的 I/O 观后感|有奖征集获奖名单
Data playback partner rviz+plotjuggler
492. Construction rectangle
I/o impressions from readers | prize collection winners list
穀歌出海創業加速器報名倒計時 3 天,創業人闖關指南提前收藏!
Replace Django database with MySQL (attributeerror: 'STR' object has no attribute 'decode')
The real definition of open source software
I/o multiplexing & event driven yyds dry inventory
Page printing plug-in print js
Leverage Google cloud infrastructure and landing area to build enterprise level cloud native excellent operation capability
Keepalived installation, use and quick start
Can't the dist packaged by vite be opened directly in the browser
PHP inner class name is the same as the inner class method name
Software testing - concept
复杂 json数据 js前台解析 详细步骤《案例:一》
[C language] simple implementation of mine sweeping game
Servlet web XML configuration details (3.0)
Compte à rebours de 3 jours pour l'inscription à l'accélérateur de démarrage Google Sea, Guide de démarrage collecté à l'avance!