재귀적 접근 방식을 사용하여 집합의 모든 하위 집합을 어떻게 찾나요?

집합의 모든 하위 집합 찾기

n개의 요소 집합이 주어지면 하위 집합은 해당 요소의 조합입니다. 목표는 가능한 모든 하위 집합을 생성하는 포괄적인 알고리즘을 찾는 것입니다.

재귀 솔루션

다음 알고리즘을 고려하세요.

• 기본 사례 : 집합에 요소가 하나만 포함된 경우 알고리즘은 빈 집합과 해당 요소를 포함하는 집합을 반환합니다. 요소.
• 재귀 단계: n 요소가 있는 집합의 경우 첫 번째 n-1 요소의 하위 집합 집합을 찾습니다.
• 분할: 이전 집합을 두 그룹으로 나눕니다. n번째 요소와 그렇지 않은 부분 집합.
• 합집합: 이 두 그룹의 합집합을 취하여 완전한 집합을 형성합니다. 하위 집합.

예: {1,2,3,4,5}

1단계: {1,2,3, 4}. 이는 다음과 같습니다: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4 }, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4} 및 {1,2,3,4} .

2단계: 1단계의 각 하위 집합에 5를 추가하고 하위 집합과 결합합니다.

• {} -> {}
• {1} -> {1} 및 {1,5}
• {2} -> {2} 및 {2,5}
• ...
• {1,2,3,4} -> {1,2,3,4} 및 {1,2,3,4,5}

이러한 하위 집합의 합집합은 {1,2,3, 4,5}:

{ {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, {1 ,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3 ,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3 ,4,5}, {2,3,4,5} 및 {1,2,3,4,5} }

위 내용은 재귀적 접근 방식을 사용하여 집합의 모든 하위 집합을 어떻게 찾나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!