首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

从unordered_set获取给定大小k的所有子集?

从unordered_set获取给定大小k的所有子集,可以通过回溯算法来实现。回溯算法是一种通过不断尝试所有可能的解决方案来求解问题的方法。

具体步骤如下:

  1. 定义一个空的结果集,用于存储所有符合条件的子集。
  2. 定义一个临时集合temp,用于存储当前正在构建的子集。
  3. 编写一个递归函数,该函数接受当前遍历的元素索引、当前已选择的元素数量和目标选择的元素数量作为参数。
  4. 在递归函数中,首先判断当前已选择的元素数量是否等于目标选择的元素数量。如果是,则将temp加入结果集。
  5. 否则,从当前元素索引开始遍历unordered_set中的元素,将元素加入temp,并递归调用函数,传入更新后的元素索引、已选择的元素数量加1和目标选择的元素数量。
  6. 在递归调用后,将temp中的最后一个元素移除,以便尝试下一个元素。
  7. 最后,返回结果集。

以下是示例代码:

代码语言:txt
复制
#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

void backtrack(unordered_set<int>& nums, vector<int>& temp, vector<vector<int>>& res, int start, int k) {
    if (temp.size() == k) {
        res.push_back(temp);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        temp.push_back(nums[i]);
        backtrack(nums, temp, res, i + 1, k);
        temp.pop_back();
    }
}

vector<vector<int>> getSubsets(unordered_set<int>& nums, int k) {
    vector<vector<int>> res;
    vector<int> temp;
    backtrack(nums, temp, res, 0, k);
    return res;
}

int main() {
    unordered_set<int> nums = {1, 2, 3, 4};
    int k = 2;
    vector<vector<int>> subsets = getSubsets(nums, k);
    
    for (const auto& subset : subsets) {
        for (const auto& num : subset) {
            cout << num << " ";
        }
        cout << endl;
    }
    
    return 0;
}

这段代码中,我们使用了一个unordered_set来存储给定的元素集合nums,然后调用getSubsets函数来获取大小为k的所有子集。最后,我们遍历结果集并输出每个子集。

这个问题没有特定的腾讯云产品与之直接相关,因此无法提供相关产品和链接。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

回溯算法:递增子序列

❞ 491.递增子序列 题目链接:https://leetcode-cn.com/problems/increasing-subsequences/ 给定一个整型数组, 你任务是找到所有该数组递增子序列...数组中整数范围是 [-100,100]。 给定数组中可能包含重复数字,相等数字应该被视为递增一种情况。 思路 这个递增子序列比较像是取有序子集。而且本题也要求不能有相同递增子序列。...这又是子集,又是去重,是不是不由自主想起了刚刚讲过回溯算法:求子集问题(二)。 就是因为太像了,更要注意差别所在,要不就掉坑里了!...return,因为要取树上所有节点 } 单层搜索逻辑 在图中可以看出,同层上使用过元素就不能在使用了,「注意这里和回溯算法:求子集问题(二)中去重区别」。...程序运行时候对unordered_set 频繁insert,unordered_set需要做哈希映射(也就是把key通过hash function映射为唯一哈希值)相对费时间,而且每次重新定义set

1.2K20

2021-08-09:给定一个有正、有负、有0数组arr,给定一个整数k,返回arr子集是否能累加出k。1)正常怎么做?2)

2021-08-09:给定一个有正、有负、有0数组arr,给定一个整数k,返回arr子集是否能累加出k。1)正常怎么做?2)如果arr中数值很大,但是arr长度不大,怎么做?...,可能为负,可能为0 // 自由选择arr中数字,能不能累加得到sum // 分治方法 // 如果arr中数值特别大,动态规划方法依然会很慢 // 此时如果arr数字个数不算多(40以内),哪怕其中数值很大...,分治方法也将是最优解 func isSum4(arr []int, sum int) bool { if sum == 0 { return true } if...rightSum) // 单独查看,只使用左部分,能不能搞出sum // 单独查看,只使用右部分,能不能搞出sum // 左+右,联合能不能搞出sum // 左部分搞出所有累加和时候...形成累加和是pre // arr[i...end - 1] end(终止) 所有数字随意选择, // arr[0...end-1]所有可能累加和存到ans里去 func process4(arr

32330

递增子序列,有点难度!

子集问题有点像,但又处处是陷阱 491.递增子序列 力扣题目链接:https://leetcode-cn.com/problems/increasing-subsequences/ 给定一个整型数组..., 你任务是找到所有该数组递增子序列,递增子序列长度至少是2。...数组中整数范围是 [-100,100]。 给定数组中可能包含重复数字,相等数字应该被视为递增一种情况。 思路 这个递增子序列比较像是取有序子集。而且本题也要求不能有相同递增子序列。...这又是子集,又是去重,是不是不由自主想起了刚刚讲过90.子集II。 就是因为太像了,更要注意差别所在,要不就掉坑里了! 在90.子集II中我们是通过排序,再加一个标记数组来达到去重目的。...return,因为要取树上所有节点 } 单层搜索逻辑 在图中可以看出,同一父节点下同层上使用过元素就不能在使用了 那么单层搜索代码如下: unordered_set uset; //

84030

400多k大小减到了2B,我APP是怎么优化

前言 本篇文章主要针对 Android性能优化 中 Android APK大小优化 虽然现在网速已经非常快,用户流量也很多,但是对于我们 Android apk 文件进行优化还是很有必要,动不动几十上百兆大小...,用户体验还是很不好,下面我们就来整理一下 Android apk 优化方法 一、icon 图标使用 svg 在我们App中会有很多icon,而且美工小姐姐一般都是成套给,所以在我们res文件中可能需要放入多套...icon,这样一来就会使我们apk文件体积变得非常大了,所以,优化第一步就从icon 处理开始. icon 尽量使用svg 文件,而不要使用png文件 首先 svg 文件是以xml文件方式存在...图片压缩体积大约只有JPEG2/3,并能节省大量服务器宽带资源和数据空间。...但400多k大小变成了2B 六、资源打包设置 由于第三方库引入,如appcompat-v7引入库中包含了大量国际化资源,可根据自身业务进行相应保留和删除 原始包如下: 原始包中存在各国语言,所以我们一般只需要保留中文即可

1.3K40

C++哈希-使用模拟封装

set快,但它通常在遍历元素子集范围迭代方面效率较低 它迭代器是单向前向迭代器 接口介绍: unordered_set当中常用成员函数 成员函数 功能 insert 插入指定元素 erase 删除指定元素...成员函数 功能 begin 获取容器中第一个元素正向迭代器 end 获取容器中最后一个元素下一个位置正向迭代器 使用示例: void test_unordered_set() { unordered_set...概念: 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址关键码归于同一子集合,每一个子集合称为一个桶,各个桶中元素通过一个单链表链接起来,各链表头结点存储在哈希表中...,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶个数时,可以给哈希表增容 科学增容:除留余数法,最好模一个素数 代码实现: //获取下一个质数(接近二倍开辟),比较科学减少冲突取扩容大小方式...10 : _table.size() * 2; size_t newsize = GetNextPrime(_table.size());//获取扩容大小 vector newdata

90320

Codeforces Round #826 (Div. 3)(A~D)

Compare T-Shirt Sizes ---- Origional Link 题目大意: 给定不同衬衫大小尺寸编号如:S,M,L。 除 M 之外,X 作为尺寸前缀代表其倍数大小。...给定两个代表衬衫尺寸字符串,判断衬衫大小。 ---- 思想: 签到题。 判断模拟即可。...求满足上述条件切分方案下,最长一个区间最小可能值。 ---- 思想: 前缀和,模拟。 1 枚举区间长度,设当前区间和为 t。 每次向后枚举找到和 t 相等区间,并且更新最长区间。...当枚举到和大于 t 区间剪枝。 枚举结束,判断是否切分掉了所有的区间,最后更新答案区间。...Masha and a Beautiful Tree ---- Origional Link 题目大意: 给定一个满二叉树(即树叶子节点数目为 2^n),叶子节点权值是 1 - n 排列,每个节点拥有不同权值

27210

Codeforces Round #826 (Div. 3)(A~D)

Compare T-Shirt Sizes ---- Origional Link 题目大意: 给定不同衬衫大小尺寸编号如:S,M,L。 除 M 之外,X 作为尺寸前缀代表其倍数大小。...给定两个代表衬衫尺寸字符串,判断衬衫大小。 ---- 思想: 签到题。 判断模拟即可。...求满足上述条件切分方案下,最长一个区间最小可能值。 ---- 思想: 前缀和,模拟。 1 枚举区间长度,设当前区间和为 t。 每次向后枚举找到和 t 相等区间,并且更新最长区间。...当枚举到和大于 t 区间剪枝。 枚举结束,判断是否切分掉了所有的区间,最后更新答案区间。...Masha and a Beautiful Tree ---- Origional Link 题目大意: 给定一个满二叉树(即树叶子节点数目为 2^n),叶子节点权值是 1 - n 排列,每个节点拥有不同权值

25830

C++进阶之哈希(unordered_mapu002Fset使用及其模拟)

unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集范围迭代方面效率 较低。...顺序查找时间复杂度为O(N),平衡树中为树高度,即O(N),搜索效率取决于搜索过程中元素比较次数 理想搜索方法是可以不经过任何比较,一次直接表中得到要搜索元素。...4 .开散列 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址关键码归于同一子集合,每一个子集合称为一个桶,各个桶中元素通过一个单链表链接起来,各链表头结点存储在哈希表中...10 : _table.size() * 2; size_t newsize = GetNextPrime(_table.size());//获取扩容大小..., class Hash = HashFunc> class unordered_set { struct SetOfKey {

56710

C++【哈希表完善及封装】

获取 key 值 单独封装为一个 仿函数,再利用 模板特化,使其既能支持 整型 也能支持 字符串 //获取 key 值仿函数 template struct GetKey { size_t...0; for (auto e : key) val += static_cast(e); return val; } }; 添加了这个仿函数之后,就需要对 哈希表 中所有需要获取...简单来说,就是当我们扩容后,按照 下一个素数值大小 进行扩容 这些素数都是近似 2 倍大小关系,在确保不会频繁扩容同时,尽可能减少哈希冲突 所以需要这样一个函数 //获取素数 size_t GetNextPrime...这个可以通过自己 值 % 哈希表大小 求出,清楚位置后,就向后移动,直到移动至一个不为空位置,返回即可 因为要获取使用 哈希表,所以需要对 迭代器类 做出一些调整 //对哈希表前置声明 template...与 unordered_map 只需要提供符合自己特色 key 获取仿函数即可,增加部分基础功能(具体函数功能实现位于 HashTable.hpp 中) unordered_set #pragma

27560

哈希简单介绍

unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集范围迭代方面效率较低。...桶操作 unordered_set 关于unordered_set介绍我就不进行讲解了,都差不多 链接: http://www.cplusplus.com/reference/unordered_set...可根据散列表大小,选择其中各种符号分布均匀若干位作为散列地址。...线性探测:发生冲突位置开始,依次向后探测,直到寻找到下一个空位置为止。...下面我们就来了解一个高效且常用办法:开散列 开散列 开散列概念 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址关键码归于同一子集合,每一个子集合称为一个桶,各个桶中元素通过一个单链表链接起来

7610

【代码随想录】二刷-回溯算法

回溯是递归副产品,只要有递归就会有回溯。 回溯法效率: 回溯法本质是穷举,穷举所有可能,然后选出我们想要答案。...回溯法一般可以解决如下几种问题: 组合问题: N个数里面按一定规则找出K个数集合 切割问题: 一个字符串按一定规则由于几种切割方式 子集问题: 一个N个数集合里有多少符合条件子集 排列问题...回溯法解决都可以抽象为树型结构。 因为回溯法解决都是在集合中递归查找子集,集合大小就构成了树宽度,递归深度构成了树深度。...具体来说, 给定一个字符串s, 长度为n, 它成为回文字串充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串。...因为频繁unordered_set进行insert操作,unordered_set需要做哈希映射(也就是把key通过hash function映射为唯一哈希值)相对费时间,而且insert时候其底层符号表也要做相应扩充

899120

哈希(unordered_map、unordered_set

例如:数据集合{1,7,6,4,5,9} 哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总大小 哈希冲突 不同关键字通过相同哈希哈数计算出相同哈希地址...那如何寻找下一个空位置 线性探测 发生冲突位置开始,依次向后探测,直到寻找到下一个空位置为止 线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同 关键码占据了可利用空位置...,每一个子集合称为一个桶,各个桶中元素通过一个单链表链 接起来,各链表头结点存储在哈希表中。...unordered_map和unordered_set封装 hash表(开散列) 几个点: 模板类,第一个模板参数是K,第二个参数T,上层决定这个T是什么 传入仿函数KeyOfT,这个可以T类型中取K...unordered_set底层也是哈希表,第二个模板参数传个K,同时要配对应仿函数,返回K就好了 #pragma once #include "hash.h" namespace st {

35220

2022-04-17:给定一个数组arr,其中值有可能正、负、0,给定一个正数k。返回累加和>=k所有子数组中,最短子数组长度。来自字节跳动。力扣8

2022-04-17:给定一个数组arr,其中值有可能正、负、0, 给定一个正数k。 返回累加和>=k所有子数组中,最短子数组长度。 来自字节跳动。力扣862。...达标的前缀和,哪一个离k最近? 单调栈+二分。复杂度是O(N*logN)。 双端队列。 时间复杂度:O(N)。 代码用rust编写。...[2, -1, 2]; let K: isize = 3; let ret = shortest_subarray2(arr, K); println!...} let mut l: isize = 0; let mut r: isize = 0; for i in 0..N + 1 { // 头部开始,符合条件,...as usize]); l += 1; } // 尾部开始,前缀和比当前前缀和大于等于尾部弹出!

1.3K10

Codeforces Round #828 (Div. 3) (A~D)

Even-Odd Increments ---- Origional Link 题目大意 给定一个序列 a 和 q 次操作: 操作 0~~x_j 表示将序列中所有的偶数加上 x_j。...操作 1~~x_j 表示将序列中所有的奇数加上 x_j。 求每次操作之后序列之和。 ---- 思想: 思维题。 记录 a 之和以及其偶数和奇数数量。...求最长等待可以遇到 g 时间。 ---- 思想: 模拟。 将 s 加长,使得一个周期首尾相连。 每个信号为 c 位置开始,找到下一个为 g 位置。 更新最大区间长度。...Divisibility by 2^n ---- Origional Link 题目大意: 给定一个长度为 n 正整数序列 a,使得所有元素乘积可以被 2^n 整除。...求满足题意最少操作次数。 ---- 思想 贪心。 设 a_i 乘积为 k,则满足 2^n | k 条件为 k 因数分解中,2 因子数量大于等于 n。

30920
领券