비트연산자 완전탐색

#부분집합의 모든 경우를 순회하며
power_set = []
n = 3
arr = [i+1 for i in range(n)]
print(arr)
for i in range(1<<n) : #1부터 12까지를 원소로 가지는 집합의 부분집합의 수는 2의 12승
    tmp_set = [] #부분집합을 담을 임시저장소
    #n만큼 j가 순회하며
    for j in range(n) :
        #i의 j번째 비트가 1인지 아닌지 확인
        if i & (1<<j) :
            #for문을 순회하며 and연산 결과 True이면 A리스트의 j인덱스를 tmpset에 추가
            #ex 13이면 1101 이니까, 1,3,4번째 비트 추가
            tmp_set.append(arr[j])
    power_set.append(tmp_set)
print(power_set)

1. 부분집합의 모든 원소를 담을 power_set 준비
2. 원래 집합 arr 준비
3. n은 arr의 길이
4. 부분집합의 원소 합은 2^n이니까 1<<n만큼 순회
5. 부분집합을 담을 임시저장소 tmp_set준비
6. 그니까 부분집합의 원소가 2의 n승개니까 비트가 n-1개 있잖아 그걸 순회
7. i를 비트로 바꿨을 때
   • (예를들어 i가 13이면 1101) j도 1000,100,10,1 이런식으로 존재
8. 그럼 0번째 비트, 2번째 비트, 3번째 비트가 겹치잖아 그럼 그 j를 인덱스로 값을 arr배열에서 찾아서 임시저장소에 넣는다.
9. 그연산이 종료되면 power_set에 넣자