집합의 모든 하위 집합 생성

주어진 집합의 모든 하위 집합을 결정할 때 요소 수(n)가 중요한 역할을 합니다. . 효과적인 알고리즘은 이를 달성하기 위해 재귀 기술을 활용합니다.

재귀 알고리즘

재귀 알고리즘은 각 요소에 대해 하위 집합을 두 개로 분할할 수 있다는 원칙에 따라 작동합니다. 카테고리: 요소를 포함하는 카테고리와 요소를 제외하는 카테고리. 이 두 파티션은 그렇지 않으면 동일한 하위 집합을 공유합니다.

n=1부터 시작하여 두 개의 하위 집합, 즉 {}(빈 집합)과 {1}이 있습니다.

n>1인 경우 다음을 결정합니다. 1,...,n-1의 하위 집합을 복제합니다. 한 세트에는 각 하위 세트에 n이 추가되고 다른 세트는 변경되지 않습니다. 이 두 집합을 결합하면 전체 하위 집합 집합이 생성됩니다.

설명 예

{1, 2, 3, 4, 5}의 하위 집합을 생성해 보겠습니다.

• n=1: {{} , {1}}
• n=2: {} , {1} 수행 그리고 2를 추가합니다. {} , {1}: {{} , {1} , {2} , {1, 2}}
• n=3: 3을 추가합니다. {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: 4 추가: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , { 1, 2, 3, 4}}
• n=5: 5 추가: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}, {5} , {1, 5} , {2, 5} , {1, 2, 5} , {3, 5} , {1, 3, 5} , {2, 3, 5} , {1, 2, 3, 5}, {4, 5} , {1, 4, 5} , {2, 4 , 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4 , 5}}

따라서 {1, 2, 3, 4, 5}의 32개 하위 집합에 모두 도달합니다.