N개의 비트에서 모든 부분집합들의 부분집합 순회하기

시간복잡도가 \(4^N\) 일 것같지만 \(3^N\) 이라고한다. 이유는 잘모르겠음 걍 외우자ㅎ

+

이유를 깨달았다

부분집합(1)의 부분집합(2)이니까

부분집합(1) 에 포함되거나 안되거나고, 만약 된다면 부분집합(2)에 포함되거나 안되거나니까 결국

1. 부분집합(1)에 포함되지만 부분집합(2)에는 포함되지않거나

2. 부분집합(1)에도 포함되고 부분집합(2)에 포함되거나

3. 둘다 안포함되거나

셋중 하나이기때문에 3^N