[LeetCode] Subsets I (78) & II (90) 解题思路,即全组合算法

时间:2022-09-15 22:10:47

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

问题: 给定一个集合,求集合元素的所有组合的情况。

实际上就是一题求全组合的题目。

nums[i...n) 的所有组合情况可以分为两种:包含nums[i] 的 和 不包含 nums[i] 的。

  • 包含 nums[i] 的:nums[i] 依次加到 nums[i+1...n) 的全部情况即可。
  • 不包含 nums[i] 的 :就是 nums[i+1...n) 的全部情况。

上面的递推关系,实际上就是 DP 思路。

     vector<vector<int>> theset;

     void regardValue(int value){

         if (theset.size() == ) {
vector<int> tmp0;
vector<int> tmp1 = {value};
theset.push_back(tmp0);
theset.push_back(tmp1);
return;
} int LofPre = (int)theset.size(); for (int i = ; i < LofPre; i++) {
vector<int> tmp = theset[i];
tmp.push_back(value);
theset.push_back(tmp);
}
} vector<vector<int>> subsets(vector<int>& nums) { std::sort(nums.begin(), nums.end()); for (int i = ; i < nums.size(); i++) {
regardValue(nums[i]);
} return theset;
}

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

问题:若集合中包含重复值,求所有的可能组合,即子集合。

要求:子集合内可以有重复值,但是子集合之间不可以有重复的子集合。

同样采用原来的思路,用 unordered_set<vector<int>> 代替 vector<vector<int>> ,就得最后结果后,再转为 vector<vector<int>> 即可。

在实现过程中发现 unordered_set<vector<int>> 不能直接使用。在 * 看到解法方法,增加对 vector<int> 结构进行 hash 即可使用。修改后,算法实现并通过。

     struct VectorHash {
size_t operator()(const vector<int>& v) const {
hash<int> hasher;
size_t seed = ;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed<<) + (seed>>);
}
return seed;
}
}; vector<vector<int>> theset; unordered_set<vector<int>, VectorHash> uniSet; void regardValue(int value){ if (uniSet.size() == ) {
vector<int> tmp0;
vector<int> tmp1 = {value};
uniSet.insert(tmp0);
uniSet.insert(tmp1);
return;
} unordered_set<vector<int>, VectorHash> cpSet = uniSet; unordered_set<vector<int>, VectorHash>::iterator t_iter; for (t_iter = cpSet.begin(); t_iter != cpSet.end(); t_iter++) {
vector<int> tmp = *t_iter; tmp.push_back(value);
uniSet.insert(tmp);
}
} vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); for (int i = ; i < nums.size(); i++) {
regardValue(nums[i]);
} unordered_set<vector<int>, VectorHash>::iterator t_iter; for (t_iter = uniSet.begin(); t_iter != uniSet.end(); t_iter++) {
vector<int> tmp = *t_iter;
theset.push_back(tmp);
} return theset; }

[LeetCode] Subsets I (78) & II (90) 解题思路,即全组合算法的更多相关文章

  1. leetCode 90&period;Subsets II(子集II) 解题思路和方法

    Given a collection of integers that might contain duplicates, nums, return all possible subsets. Not ...

  2. &lbrack;LeetCode&rsqb; Course Schedule I &lpar;207&rpar; &amp&semi; II &lpar;210&rpar; 解题思路

    207. Course Schedule There are a total of n courses you have to take, labeled from 0 to n - 1. Some ...

  3. &lbrack;LeetCode&rsqb; Search in Rotated Sorted Array I &lpar;33&rpar; &amp&semi;&amp&semi; II &lpar;81&rpar; 解题思路

    33. Search in Rotated Sorted Array Suppose a sorted array is rotated at some pivot unknown to you be ...

  4. leetCode 81&period;Search in Rotated Sorted Array II (旋转数组的搜索II) 解题思路和方法

    Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this ...

  5. leetCode 82&period;Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法

    Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numb ...

  6. &lbrack;LeetCode&rsqb; 74&period; Search a 2D Matrix 解题思路

    Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the follo ...

  7. &lbrack;LeetCode&rsqb; 347&period; Top K Frequent Elements 解题思路 - Java

    Given a non-empty array of integers, return the k most frequent elements. For example,Given [1,1,1,2 ...

  8. &lbrack;LeetCode&rsqb; 307&period; Range Sum Query - Mutable 解题思路

    Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive ...

  9. leetCode 86&period;Partition List&lpar;分区链表&rpar; 解题思路和方法

    Given a linked list and a value x, partition it such that all nodes less than x come before nodes gr ...

随机推荐

  1. ue4 UE4Editor&period;lib找不到

    PublicDependencyModuleNames里加了Launch后,会导致链接UE4Editor.lib, 但这个文件在预编版的引擎里是没有的(奇怪的是自己编译引擎的话会有) 如果只是要头文件 ...

  2. Test Android with QTP

    by Yaron Assa I have recently come across a plug-in to QTP that enables to automate tests on Android ...

  3. 编译android程序时DEX过程出现错误

    今天编译高级设置时出现了错误,这好坑爹啊~ 于是我开始检查代码,发现代码没有错误啊,然后观察MAKE的步骤才发现是DEX时出现了问题!! 下面是错误的LOG: Information:Using ja ...

  4. Codeforces Beta Round &num;80 &lpar;Div&period; 1 Only&rpar; D&period; Time to Raid Cowavans 离线&plus;分块

    题目链接: http://codeforces.com/contest/103/problem/D D. Time to Raid Cowavans time limit per test:4 sec ...

  5. poj 2479 &lpar;DP&rpar;

    求一个区间内连续两段不相交区间最大和. // File Name: 2479.cpp // Author: Missa_Chen // Created Time: 2013年06月22日 星期六 16 ...

  6. Elasticsearch升级至1&period;x后API的变化-三

    请支持原创:http://www.cnblogs.com/donlianli/p/3841762.html   1.索引格式 1.x之前的版本,被索引的文档type会同时出现在url和传输的数据格式中 ...

  7. WildMagic 简单图元&lpar;一&rpar;

    #include <Wm5WindowApplication3.h> #include <Wm5VisualEffectInstance.h> using namespace ...

  8. JS的DOM操作及动画

    JS的DOM操作DOM:Document Object ModelBOM:Bowers(浏览器) Object Model找到元素:var a=document.getElementById(&quo ...

  9. 层居中绝对定位的div的居中方法,下面的写法兼容IE系列浏览器和火狐浏览器

    详细解说,直接看样式:#dingwei{padding:10px;background-color:#003300;color:#FFFFFF; width:600px;height:300px; d ...

  10. WEB站点服务器安全配置

    WEB站点服务器安全配置   本文转自:i春秋社区   // 概述 // 熟悉网站程序 // 更改默认设置的必要性 // 目录分析与权限设置技巧 // 防止攻击其他要素 // 公司官网不可忽视的安全性 ...