[Algorithm Study] 파이썬 부분집합 구하기 예시

반복문을 이용해 부분집합 구하기

arr = list(map(int, input().split()))
subsets = [[]]

for i in arr:
    L = len(subsets)
    for l in range(L):
        subsets.append(subsets[l] + [i])

print(subsets)

 

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

arr = list(map(int, input().split()))

n = len(arr)

for i in range(1<<n):
	li = []
    for j in range(n):
    	if i & (1 << j):
        	li.append(arr[j])
            
    print(li)

• 1<<n : 2^n-1을 을 표현한다. 컴퓨터가 2진법에서 001로 인식하고 있는 숫자 1을 왼쪽으로 n만큼 이동시킨다.
  ex) 1<<3 : 0001 → 0010 → 0100 → 1000
      2진법에서 1000, 10진법에서 16 = 2^4 = (2^(1+3)) 
• & : 교집합과 같은 기능