当前位置: 首页 > 面试题库 >

查找所有总计为给定数字的子集

庾远航
2023-03-14
问题内容

我正在学习Python,对此问题似乎很简单。

我想找到所有总计给定数字的可能组合。
例如:4-> [1,1,1,1] [1,1,2] [2,2] [1,3]

我选择生成所有可能子集(2 ^ n)的解决方案,然后得出总和等于数字的那些子集。我的状况有问题。码:

def allSum(number):
    #mask = [0] * number
    for i in xrange(2**number):
        subSet = []
        for j in xrange(number):
            #if :
                subSet.append(j)
        if sum(subSet) == number:
           yield subSet



for i in allSum(4):
    print i

BTW是个好方法吗?


问题答案:

这是几年前我看到的一些实现此目的的代码:

>>> def partitions(n):
        if n:
            for subpart in partitions(n-1):
                yield [1] + subpart
                if subpart and (len(subpart) < 2 or subpart[1] > subpart[0]):
                    yield [subpart[0] + 1] + subpart[1:]
        else:
            yield []

>>> print list(partitions(4))
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]

其他参考:

  • http://mathworld.wolfram.com/Partition.html
  • http://en.wikipedia.org/wiki/Partition_(number_theory)
  • http://www.site.uottawa.ca/~ivan/F49-int-part.pdf


 类似资料:
  • 我有N个数字,让我们说。现在我想找出在给定范围内有多少对数字。(L和R给定)。数字对=两个数字相同。我的方法:

  • 使用递归,编写一个给定整数列表和给定和的程序,将找到总数为给定和的所有数字子集。计算找到的子集数。如果不存在子集,则应指示未找到解决方案。例如,给定列表6、13、3、3,且总和为19,您的程序应找到两个解决方案: 将输入列表中的整数数限制为最多20个整数。仅接受正整数,并使用0标记列表的结尾。以下是运行示例: 这是我的代码,但它只找到一个子集,我想找到所有子集。有什么帮助吗?

  • 问题内容: 给定一个非负整数数组和一个数字。您需要打印总和等于给定整数的子数组的所有开始和结束索引。 例如 : Explanation : [3, 6] [9], [9,0] These all are the subarrays with their sum equal to 9. 问题答案: 解决这个问题的基本蛮力方法是生成给定数组的所有子数组,然后遍历生成的子数组并计算总和,如果这个总和等于

  • 我知道强力解O(n^2),我想要另一个解O(n),还是O(n,log,n)?

  • 问题内容: 我正在为Android开发一个数学应用程序。在这些字段之一中,用户可以输入一个整数(无数字且大于0)。这个想法是获得所有可能的和,使之成为整数,而不加倍(在这种情况下为4 + 1 == 1 + 4)。唯一已知的是此int。 例如: 假设用户输入4,我希望该应用返回: 4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 显然4 == 4,所以也应该加上。关于我应该

  • 我遇到了一个问题语句,要在给定的两个子字符串之间找到所有公共子字符串这样一种方式,在每种情况下都必须打印最长的子字符串。问题声明如下: 编写一个程序来查找两个给定字符串之间的公共子字符串。但不包括包含在较长公共子字符串中的子字符串。 null 在这种情况下,您不必使用字符串实用程序方法,如:contains、indexOf、StringTokenizer、split和replace。 我的算法是这

  • 我一直在学习动态规划,我想通过打印出所有相加为一个数字的子集来进一步研究经典的子集和问题。我该怎么做呢?到目前为止,我知道如何根据是否存在相加的子集来打印true或false 如果可能,我想返回所有子集的数组。

  • 本文向大家介绍JavaScript查找范围内所有数字的总和,包括了JavaScript查找范围内所有数字的总和的使用技巧和注意事项,需要的朋友参考一下 问题 我们需要编写一个JavaScript函数,该函数接受一个指定范围的数组。 我们的函数应该找到并返回落在该范围内的所有自然数之和,包括范围数。 示例 以下是代码- 输出结果 以下是控制台输出-