[APS] 10. Python으로 부분집합 만들기

1. 비트연산자를 이용해서 부분집합 구하기

이 방법은 저번 포스팅에서 다뤘으니, 자세한 설명은 아래 링크를 참고하면 된다.

arr = [3,6,7,1,5,4]
n = len(arr)

for i in range(0, (1<<n)):  # 부분집합의 수 만큼 반복한다.
    for j in range(0, n):   # 원소의 수만큼 비트를 비교한다
        if i & (1<<j):  # i의 j번째 비트가 1이면 포함되었다는 의미이다. 
            print(arr[j], end="")   # arr[j]를 프린트 한다.
    print()

2. 재귀함수를 이용해서 만들기

def f(i, k):
    if i==k:
        for j in range(k):
            if bit[j]:
                print(arr[j], end=" ")
        print()
    else:
        bit[i] = 0
        f(i+1, k)
        bit[i] = 1
        f(i+1, k)

arr = [3, 6, 7, 1]
n = len(arr)

bit = [0] * n
f(0, n)

Uploaded by N2T