leetcode.com 78. Subsets

문제 링크: https://leetcode.com/problems/subsets/description/

파이썬 소스: https://bit.ly/3VY2v9T

 

문제에서는 ‘return all possible subsets’이라고 표현했습니다. 즉, 가능한 모든 부분집합을 리턴한다. 라는 뜻입니다. 하지만, Example 1번의 Output의 순서를 조금 바꿔보면, 조합(combination)문제라는 것을 알 수 있습니다.

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

여기서, 원소가 없는 빈 리스트는 잠시 제외를 하구요.

[[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

리스트의 길이가 짧은 원소를 앞으로 이동시켜 보겠습니다. [3]이 앞으로 이동합니다.

[[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

리스트의 길이 별로 길이 1, 2, 3으로 나눠 보겠습니다. 그러면, nums을 사용해서 만들 수 있는 길이가 1~3까지의 조합이라는 것을 알 수 있습니다.

[1],[2],[3] <- 길이가 1인 조합

[1,2],[1,3],[2,3] <- 길이가 2인 조합

[1,2,3] <- 길이가 3인 조합

부분 집합을 구하는 문제인 것 같았지만, 사실은 조합을 구하는 문제가 되었습니다. 이 문제를 풀이할 때, 조합을 구현하지 않고, itertools의 combinations을 사용해도 되지만, 이 번 풀이에서는 조합을 직접 구현해보도록 하겠습니다.

 

def rec(nums: List[int], idx_begin: int, length: int, pathes: List, answer: List):     if length == 0:         if pathes not in answer:             answer.append(pathes)         return     for idx in range(idx_begin, len(nums)):         n = nums[idx]         rec(nums, idx + 1, length - 1, pathes + [n], answer)     return answer

- 조합을 구할 숫자가 들어 있는 리스트 nums 배열

- Idx_begin: nums리스트에서 가지고 올 첫번째 숫자의 인덱스입니다. 조합에서는 순서를 고려하지 않기 때문에, pathes에 한 숫자는 1개만 들어올 수 있습니다. 따라서, rec()를 재귀호출 할 때 마다, idx +1을 해서, 한 숫자가 중복해서 pathes에 들어가지 않도록 합니다.

조합에 넣을 숫자를 가지고 올 때, range(idx_begin, len(nums))로 구현되어 있습니다. 즉, 이전에 넣은 숫자의 다음 숫자부터 조합에 넣게 됩니다.

- length 구할 조합의 길이

- pathes 구하고 있는 중인 조합

- answer: 구한 조합을 저장할 리스트

위의 코드와 같이, 한번 rec()함수를 호출할 때 마다, 조합에 들어가는 숫자 1개를 찾을 수 있고, 길이가 0이 될 때 까지, rec() 함수를 호출 하면, nums에 대한 길이 length의 조합을 구할 수 있습니다.

class Solution:     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:         answer = []         nums.sort()         for length in range(len(nums) + 1):             answer_local = []             mycombination(nums, length, answer_local)             answer += answer_local         return answer

문제에서는 집합(set)을 구하는 것이기고, any order 라고, 순서도 관계 없다고 되어 있지만, 디버깅을 좀 편하게 하기 위해서, nums를 정렬을 해줍니다.

 

이 글의 시작에서 설명한 것 처럼, 길이 0부터 길이 len(nums)까지의 조합을 구해서, answer_local에 저장하구요, 구한 answer_local을 answer에 더해 줍니다.

마지막으로 answer를 리턴하면, 이문제의 답을 구할 수 있습니다.

 

 위의 문제 풀이를 바탕으로, 구현한 전체 코드는 아래와 같습니다.

from typing import List def mycombination(nums: List[int], length: int, answer: List):     def rec(nums: List[int], idx_begin: int, length: int, pathes: List, answer: List):         if length == 0:             if pathes not in answer:                 answer.append(pathes)             return         for idx in range(idx_begin, len(nums)):             n = nums[idx]             rec(nums, idx + 1, length - 1, pathes + [n], answer)         return answer     rec(nums, 0, length, [], answer)     return answer class Solution:     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:         answer = []         nums.sort()         for length in range(len(nums) + 1):             answer_local = []             mycombination(nums, length, answer_local)             answer += answer_local         return answer

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul