给定数组形式的未排序整数集,找到所有可能的子集,其总和大于或等于const整数k,例如: - 我们的集合是{1,2,3},k = 2
可能的子集: -
{2},
{3},
{1,2},
{1,3},
{2,3},
{1,2,3}
我只能想到一个简单的算法,它列出了集合的所有子集,并检查子集的和是否> = k,但是它的指数算法并列出所有子集需要O(2 ^ N).我可以使用动态编程在多项式时间内解决它吗？
假设有n个级别,在每个级别中你可以选择两个可能的字符中的一个,打印所有可能的字符串,
例如: -
假设我们有3个级别: -
level1: - ab
level2: - cd
level3: - ef
可能的字符串是: - 1. ace
2. acf
3. ade
4. adf
5. bce
6. bcf
7. bde
8. bdf
我知道样本空间是2 ^ n所以所需的时间是O(2 ^ n),但我无法弄清楚如何编写它.有什么可能的方法和我必须阅读哪些主题来解决这些问题？