8.4 부분집합

문제 

어떤 집합의 부분집합을 전부 반환하는 메서드를 작성하라

 

해결법

우선 시간복잡도와 공간복잡도를 한번 알아보자

한 집합의 부분집합은 얼마나 될까? n개의 원소가 있다고 할때 그 부분집합에 있거나, 없거나 2가지 경우에 대한 경우의 수이기 때문에 2^n개이다. 그렇다면 모든 부분집합의 리스트를 반환하는 경우에는 공간이 얼마나 차지할까? 각 원소는 전체 부분집합에 1/2에 속하게 된다. 그러면 각 원소들은 2^(n-1)개씩 존재할 것이고 원소의 갯수를 n이라고 하면 n * 2^(n-1)의  공간복잡도를 차지하게 될 것이다. 

 

1. 재귀적으로 해결하기

 이 문제는 초기사례로부터의 확장을 적용하기 좋은 문제이다. 

S = { a1, a2, a3 ...} 라고 했을때 

a1을 가지고 만들 수 있는 부분집합  : {} ,{a1}

a1, a2를 가지고 만들 수 있는 부분집합 :  {} ,{a1}, {a2} ,{a1,a2}

a1, a2, a3를 가지고 만들 수 있는 부분집합 : {} ,{a1}, {a2}, {a3} ,{a1,a3}, {a2,a3}  ,{a1,a2} ,{a1,a2,a3}

a2까지의 부분집합과 a3까지의 부분집합의 차이를 보면 기존의 부분집합들에 a3가 포함된 집합들이 추가 되었다.

이 규칙을 보면 P(n-1)까지 만들고나서 그 결과를 복사해서 an을추가하면 P(n)이 되는 것을 알 수 있다. 

def Solution(array):
    return getSubsets(array, 0)

def getSubsets(array, i):
    if (len(array)-1) == i :
        return [[],[array[i]]]
    
    prev_sets = getSubsets(array, i+1)
    new_sets = list(prev_sets)
    for j in range(len(new_sets)):
        new_sets[j].append(array[i])

    return prev_sets + new_sets

2. 조합론으로 해결하기

모든 경우의 수는 2^n개가 존재한다고 하였다. 그말은 각각의 원소에 대해 집합에 속하는지, 속하지 않는지 두가지 선택을 할 수 있고 따라서 각 부분집합은 모든 요소들에 대해 {'yes','yes','no','no'} 이런식으로 표현될 수 있다.

따라서 모든 부분집합을 만들어 내는것은 사실 이진수를 만들어 내는 것과 같다. 1부터 2^n까지의 모든 정수의 이진 표현을 집합으로 표현하면 된다. 

def Solution(array):
    subsets = []
    max = 1 << len(array)
    for i in range(max):
        subsets.append(getNumtoSubset(i, array))
    return subsets


def getNumtoSubset(k, array):
    subset =[]
    i = 0
    while k > 0:
        if k & 1 == 1:
            subset.append(array[i])
        i +=1
        k >>=1
    return subset