ch12-6(leetcode 78). 부분 집합

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 78번 ( https://leetcode.com/problems/subsets/ )

 

풀이 1. 

원소들의 집합 nums이 매개변수로 주어졌을 때 nums의 원소로 만들 수 있는 모든 부분집합들을 리턴하는 문제이다. 

 

이전에 풀었던 조합 문제에다가 로직을 추가하는 방법으로도 풀 수 있다. 

dfs(elements, start, k)

 

이전에 중첩 함수 dfs()를 선언하는 방식으로 배열과 숫자 k가 주어졌을 때 배열에서 k개의 요소를 조합하는 문제를 풀었었다. 조합은 순열처럼 순서를 고려하지 않기 때문에, 앞에 온 원소가 포함되는 조합의 경우를 모두 고려하였다면 나머지 남은 경우에서는 앞의 원소가 포함되지 않는다. (조합의 합 문제와 같은 원리이다.)

그래서 이번에도 중첩 함수 dfs()를 그대로 사용한다. 

 

부분집합은 원소가 0개인 공집합부터 n개의 모든 원소가 들어있는 집합까지를 전부 포함한다. 

 

nums = [1, 2, 3]일 때를 예로 들어보자. nums의 부분집합에 포함되는 원소들은 다음과 같다. 

- 원소가 0개인 공집합: [] => combination(nums, 0)

- 원소가 1개인 집합: [1], [2], [3] => combination(nums, 1)

- 원소가 2개인 집합: [1, 2], [2, 3], [1, 3] => combination(nums, 2)

- 원소가 3개인 집합: [1, 2, 3] => combinations(nums, 3)

이렇게 총 8개의 집합 원소들이 부분집합에 포함된다. 

 

더 확장해서 nums = [A1, A2, A3, ... , An]인 경우도 마찬가지다. 

조합에서 0개를 뽑는 경우부터 n개를 뽑는 경우까지를 for loop로 계산하고 각각 더해준다. 

 

전체 코드는 다음과 같다. 

class Solution(object):

    def subsets(self, nums):

        subset = [[]] 
        result = []
        
        # nested function for combination calculation
        def dfs(elements, start, k):
            if k == 0:
                result.append(elements[:])
                return

            for i in range(start, len(nums)):
                elements.append(nums[i])
                dfs(elements, i+1, k-1)
                elements.remove(nums[i])

        # combination(nums, 0) to combination(nums, n)
        for j in range(1, len(nums)+1):
            result = []
            dfs([], 0, j)
            subset.extend(result[:])

        return subset

 

+ 또한 두 개의 리스트 L1, L2가 있을 때 L1 뒤에 L2를 이어 붙이고 싶다면 extend()를 사용한다. 

L1.extend(L2)

 

풀이 2. (교재 참조)

위의 풀이처럼 DFS를 사용해서 더 간단하게 문제를 풀 수 있다. 

nums의 원소들로 트리를 그려 놓고, 트리를 DFS로 탐색할 때의 모든 탐색 경로를 부분집합으로 볼 수도 있다. 

 

nums = [A1, A2, A3, A4]일 때, 4개의 forest의 root는 각각 A1, A2, A3, A4이다. 

이 4개의 forest들이 하나의 root를 둔 전체 트리로 합쳐진다고 생각하자. 

그리고 그 트리를 DFS로 탐색한다고 해 보자. 

 

1. combinations(nums, 0)

root 노드를 제외하고는 어떤 노드도 탐색되지 않은 상황이다. 

 

2. combinations(nums, 1)

root 노드에서 한 칸 탐색할 수 있는 모든 경우이다. 

부분집합에서 1개의 원소가 들어있는 집합들이 여기에 해당한다. 

 

3. combinations(nums, 2)

root 노드에서 두 번 DFS를 실행했을 때 가능한 경우이다. 

부분집합에서 2개의 원소가 들어있는 집합들이 여기에 해당한다. 

 

4. combinations(nums, 3)

root 노드에서 DFS를 세 번 실행한 경우이며, 부분집합에서 3개의 원소가 들어있는 집합들이 여기에 해당한다. 

 

5. combinations(nums, 4)

root 노드에서 DFS를 네 번 실행한 경우이며, 여기서는 nums의 원소가 총 4개이므로 DFS 탐색이 가능한 최대 범위이다. 따라서 모든 원소들이 포함되어 있다.