[알고리즘 연습] 멱집합

멱집합 구하기

• 숫자 n을 입력받고 1~n의 수를 원소로 가지는 집합의 멱집합을 구한다.
• 멱집합를 하나씩 출력한다.
• 단, 출력 순서는 [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] 과 같은 패턴을 가져야 한다.

---

풀이

def getPowerSet(n,k):
    if n == k:
        return [[k]]

    basic = k        
    result = [[basic]]
    k += 1
    while (n >= k):
        for i in getPowerSet(n,k):
            result.append([basic] + i)
        k += 1

    return result

def powerSet(n) :
    result = []
    for i in range(1,n+1):
        result += getPowerSet(n,i)
    return result

def main():
    n = int(input())

    result = powerSet(n)

    for line in result :
        print(*line)

• 시작 원소가 k인 부분집합 부분을 구하는 getPowerSet 함수가 핵심적 역할을 한다.
• n과 k가 같을 경우엔 k보다 작은 집합들에 다른 부분집합이 모두 포함되었을 것이므로 [[k]]만을 리턴한다.
• 그 외엔 현재 k를 기준(basic)으로 하고, 현재의 k보다 크고 n보다는 같거나 작은 getPowerSet을 모두 현재의 k와 함께 뒤에 붙이는 재귀함수의 형태로 구한다.
• 그렇게 구한 getPowerSet을 1~n까지 적용하면 된다.