목록의 모든 하위 집합을 찾는 방법. 내가 a list [1,2,3,4]및 c = 5 라고 가정합니다 .
그래서 subsest는 {3,2}, 그리고{4,1}
요소를 두 번 고려하고 싶지 않으므로 고려하지 않을 {1,2,3}것입니다.
미리 감사드립니다.
dfs 승인을 사용하여 모든 하위 집합을 계산할 수 있습니다. index가 len (nums)과 같을 때 dfs 함수에서 부분 집합이 발견되었다고 가정 할 수 있습니다.
이제 먼저 하위 집합의 합계를 계산하고 이것이 목표와 같은지 확인합니다. 그렇지 않으면 출력 결과에 추가하지 않습니다.
이것이 같으면 현재의 모든 항목을 방문하지 않았는지 확인합니다. 모두 방문하지 않으면 출력 목록에 추가합니다.
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
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다