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

Question

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

因此子列表将是{3,2}和{4,1}

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

提前谢谢。

Answer 1

我们可以使用dfs-approve来计算所有子集。在dfs函数中，当index等于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

Answer 2

您可以尝试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)]
>>>