Блог

Как я могу найти все подмножества списка. предположим, у меня есть a list [1,2,3,4] и c = 5 ,

таким образом, подмножество будет {3,2} , и {4,1}

я не хочу рассматривать элемент дважды, поэтому {1,2,3} не буду рассматривать

Заранее спасибо .

Мы можем использовать 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
 

Вы можете попробовать 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)]
>>>