腾讯云

开发者社区

文档建议反馈控制台

首页

文章/答案/技术大牛

发布

社区首页 >问答首页 >(可能是NP-Hard)找出集合的子集总数，这样当每一个子集与其所有元素相乘时，其值都大于X。

问(可能是NP-Hard)找出集合的子集总数，这样当每一个子集与其所有元素相乘时，其值都大于X。
EN

Stack Overflow用户

提问于 2017-05-14 16:49:33

回答 1查看 489关注 0票数 2

有一个大小为arr的数组n。那么，有多少2^n子集的总乘积大于一个数字，比如说X？

n在2^5左右，X可以在2^60左右更大(只要适合于C++ long变量)

我认为类似于子集和的东西会起作用，但我现在并不这么认为。

我从Codeforce的这个问题来自过去的一场比赛那里想过这个问题。虽然这个问题不需要我所要求的，但我很好奇。

c++

algorithm

性能强劲，每月20元起的MySQL

功能完善，便宜稳定，没有业务可以自动停机，强效降本的MySQL

回答 1

Stack Overflow用户

发布于 2017-05-14 23:27:42

您的问题可以按原样通过动态编程来解决，即不使用日志。

当输入整数以二进制(而不是一元)的形式给出时，在非自适应的2-查询缩减下，您的问题是NP-硬的，因为：

乘积等于X的子集数 = 乘积大于X-1的子集数 − 乘积大于X的子集数。

我没有立即看到任何方式显示实际NP-硬度(即，在1-查询减少)。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/43970179

复制

回溯树求集合全排列和所有子集

编程算法大数据机器学习

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有，分而治之，深度搜索，动态规划，回溯，贪心等，结合这些思想再去思考如今很火的大数据，云计算和机器学习，是不是也别有一番风味呢？踏上算法之路，风景这边独好！ 01 — 通过这篇文章，你学到什么通过这篇文章，我们可以进一步体会到深度优先搜索算法在具体问题中的应用，通过详细地示意图，深刻明白递归调用时的进栈，出栈过程；最后通过Leetcode 相似解法的题目进一步加深对深度搜索算法的理解。 02 — 搜索算法搜索算法，常见的几种形式，深度优先，

double

2018/04/02

1.1K0

java 判断子集_java – 获取集合子集的策略

fetch join list session time

我有一个场景,我的应用程序可以访问有限时间窗口的会话,在此期间它必须从数据库中获取数据到内存中,然后只使用内存中的数据来处理请求.

用户7886150

2021/04/29

1.1K0

傻瓜方法求集合的所有子集问题（java版）

java

给定任意长度的一个集合，用一个数组表示，如{"a", "b","c"}，求它的所有子集。结果是{ {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}和一个空集。

天涯泪小武

2019/01/17

9740

回溯n个元素的子集

count int scanf stdio 测试

#include <stdio.h> int n; int a[100];//测试100个元素以内 int count; int f(int k) { if (!k) { int i; printf("{"); for (i = 1; i <= n; ++i) { if (a[i]) { printf("%d", i); } } printf("}\n"); ++count; } else { int i; for (i = 0;

砖业洋__

2023/05/06

2520

LeetCode 1863. 找出所有子集的异或总和再求和（DFS）

https 网络安全编程算法

一个数组的异或总和定义为数组中所有元素按位 XOR 的结果；如果数组为空，则异或总和为 0 。

Michael阿明

2021/09/06

6500

C++经典算法题-m 元素集合的n 个元素子集

algorithm position 集合

假设有个集合拥有m个元素，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有那些？

cwl_java

2020/02/13

9530

730. 所有子集的和递归

编程算法

给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和样例

和蔼的zhxing

2018/09/04

6740

子集

编程算法

给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

WindRunnerMax

2020/09/22

5200

[Leetcode][python]Subsets/Subsets II/子集/子集 II

python html 编程算法

参考： https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html 举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。

蛮三刀酱

2019/03/26

1.1K0

【python-leetcode90-子集】子集Ⅱ

编程算法

输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

西西嘛呦

2020/08/26

7200

Leetcode|子集|90.子集II（排序+first索引+跳过重复元素）

排序索引

1 回溯法（排序+first索引+跳过重复元素） class Solution { private: int size; vector<vector<int>> solution; vector<int> path; public: void backtrack(vector<int>& nums, int first) { solution.emplace_back(path); // 2. 使用first索引 for

SL_World

2021/09/18

2400

向量取子集和元素的修改方法

html date document output title

---title: "向量取子集和元素的修改方法"output: html_documentdate: "2023-03-09"---1.向量取子集的方法——用"[]"中括号取子集（1）按照逻辑值取子集：中括号里是与x等长且一一对应的逻辑值向量将TRUE对应的值挑选出来，FALSE对应的值丢弃x <- 8:12x[x==10]## [1] 10x[x<12]## [1] 8 9 10 11x[x %in% c(9,13)]## [1] 9（2）按照位置取子集：中括号里是单独的下标或由下标组成的向量x <

小叮当aka

2023/03/18

6570

【python-leetcode78-子集】子集

编程算法

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

西西嘛呦

2020/08/26

6340

所有子集剑指 Offer II 079

vector 变量递归数组调试

给定一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

叶茂林

2023/07/30

1360

LeetCode - 子集

https 网络安全编程算法

原题地址： https://leetcode-cn.com/problems/subsets/

晓痴

2019/07/24

6790

LeetCode | 子集

leetcode 数组

题目 78. 子集 - 力扣（LeetCode）给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。示例 1：

yiyun

2023/04/06

3380

LintCode 带重复元素的子集题目代码

其他

题目给定一个可能具有重复数字的列表，返回其所有可能的子集注意事项子集中的每个元素都是非降序的两个子集间的顺序是无关紧要的解集中不能包含重复子集样例如果 S = [1,2,2]，一个可

desperate633

2018/08/22

5650

Leetcode|子集|78. 子集（回溯+first索引）

递归内存数学

简而言之，就是[1, 2, 3]包含[1, 2]的子集，通过递归实现。但时间复杂度过高，为 O(N⋅2N)，因此我在力扣上提交也显示内存超时，但为了学习还是把代码放出来

SL_World

2021/09/18

3450

两种求集合全部子集的方法

编程算法 https java 网络安全

如果我们有一个求集合的所有子集(包括集合自身)的需求，即有一个集合s,包括两个元素 <a,b>，则其所有的子集为<a,ab,b>.

全栈程序员站长

2022/07/10

8550

点击加载更多

相似问题

Meteor :订阅集合子集&集合总数

确定所有值都相同的子集

所有子集的集合

相乘的每一个子集的加法

子集总数

活动推荐

提供大模型在企业的应用构建、高效便捷

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

社区富文本编辑器全新改版！诚邀体验～

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验