어떤 집합의 모든 부분집합을 멱집합이라고 부릅니다. 예를 들어 집합 {1, 2, 3}이 있다고 했을 때 집합 {1, 2, 3}의 모든 부분집합을 구하면 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이렇게 나열할 수 있고 개수는 8개입니다. 모든 부분집합을 나열하는 방법은 다음과 같은 단계로 구할 수 있습니다. 나열 방법에서 단계를 나누는 기준은 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지로 단계를 구분합니다.
Step A: 1을 제외한 {2, 3}의 부분집합을 나열합니다.
Step B: 2를 제외한 {3}의 부분집합을 나열합니다.
Step C: 3을 제외한 {}의 부분집합을 나열합니다. → {}
Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열합니다. → {3}
Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열합니다.
Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면 {}의 모든 부분집합에 {2}를 추가한 집합들을 나열하고 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열합니다. → {2}, {2, 3}
Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열합니다.
Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면 {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하고 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열합니다.
Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면 {}의 모든 부분집합에 {1}을 추가한 집합들을 나열하고 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열합니다. → {1}, {1, 3}
Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면 {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열하고 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열합니다. → {1, 2}, {1, 2, 3}
원소가 있는지, 없는지 2가지 경우를 고려하기 때문에 집합의 요소가 n 개일 때 모든 부분집합의 개수는 2n 개가 됩니다. 예를 들어 집합의 원소가 4개라면 모든 부분집합의 개수는 24, 5개라면 25가 됩니다. 간단히 {1, 2, 3}의 모든 부분집합을 구하는 단계가 다소 복잡해 보입니다. 그렇지만 어디서 많이 본 듯한 패턴이지 않나요?
우리가 앞서 배웠던 트리와 비슷한 모양을 떠올릴 수 있습니다.
멱집합을 구하는 방법에서 단계를 유심히 보면 순환 구조를 볼 수 있습니다. 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법입니다. 즉, 문제를 작은 단위로 줄여나가는 재귀의 응용으로 활용됩니다. 예를 들어 PowerSet이라는 멱집합의 개수를 구하는 함수를 작성한다면 PowerSet 함수에서 자기 자신을 호출하며 문제를 작게 줄여나갈 수 있습니다. 최소 단위로 줄어들고 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있습니다.
