如何计算大于等于 c 的列表的所有可能子集

Question

如何找到列表的所有子集。假设我有一个 list [1,2,3,4] 和 c=5 ,

所以子集将是 {3,2} 和 {4,1}

我不想考虑一个元素两次所以{1,2,3}不会考虑

提前致谢。

Answer 1

您可以尝试 itertools.combinations 理解 list：

>>> from itertools import combinations
>>> lst = [1,2,3,4]
>>> [i for n in range(len(lst) + 1) for i in combinations(lst, n) if sum(set(i)) == 5]
[(1, 4), (2, 3)]
>>>

Answer 2

我们可以使用 dfs approve 来计算所有子集。在 dfs 函数中，当索引等于 len(nums) 时，我们可以假设找到了子集。

现在我们首先计算子集的总和，然后检查它是否等于目标，如果不等于我们不会将其添加到我们的输出结果中。

如果相等，那么我们将验证是否未访问curr 的所有项目。如果都没有访问，那么我们将把它添加到输出列表中。

class Solution:
    
    def dfs(self, nums, index, curr, res):
        if index == len(nums):
            if sum(curr) != self.target:
                return
            flag = 0
            for item in curr:
                if self.visited[nums.index(item)]:
                    flag = 1
                    break
            if flag == 0:
                for item in curr:
                    self.visited[nums.index(item)] = True
                res.append(curr[:])
            return
        curr.append(nums[index])
        self.dfs(nums, index + 1, curr, res)
        curr.pop()
        self.dfs(nums, index + 1, curr, res)
        return
    
    def subsets(self, nums: List[int], target) -> List[List[int]]:
        res = []
        curr = []
        self.target = target
        self.visited = [False] * len(nums)
        self.dfs(nums, 0, curr, res)
        return res

如何计算大于等于 c 的列表的所有可能子集

How to count all the possible subsets of a list greater than equal to c

python

algorithm

dynamic-programming

python-3.x