부분집합에 대한 이해

부분집합 알고리즘

for i in range(1,1<<n):
        sum, cnt = 0, 0
        for j in range(len(arr)):
            if i & (1<<j): #각 부분집합들을 표현해 주는 것
                sum += arr[j] # 부분집합 원소들의 누적 합
                cnt += 1 #cnt는 부분집합의 원소의 개수

1<<j 동작 방식

1<<0 : $(1)_2 => (1)_2$ = 1

1<<1 : $(1)_2 => (10)_2$ = 2

1<<2 : $(1)_2 => (100)_2$ = 4

1<<3: $(1)_2 => (1000)_2$ = 8

순서

(i,j), i & (1<<j)
(1, 0), 1 : 1 = $(1)_2$ = 1 , $(1)_2$ = 1 ⇒ 1 이 되서 True
(4, 2), 4 : $(100)_2$ = 4가 되서 ture

(17,0), 1: $(1)_2$ = 1이 되서 True

왜? 부분 집합 표현을 위해 이러한 식을 사용하는가?

해당 코드를 사용한 문제

swea D3 4837 부분집합 합 구하기

```
t= int(input())
arr = list(range(1,13))
N = len(arr)
for tc in range(1,t+1):
n,k = map(int,input().split())

ans = 0
for i in range(1,1<<n):
    sum, cnt = 0, 0
    for j in range(len(arr)):
        if i & (1<<j):
            sum += arr[j]
            cnt += 1
            print((i,j),1<<j)

    if sum == k and cnt == n:
        ans += 1
print(f'#{tc} {ans}')
```