재귀적 접근 방식을 사용하여 n개의 요소가 포함된 집합의 가능한 모든 하위 집합을 어떻게 찾을 수 있습니까?

집합의 모든 부분 집합 찾기

컴퓨터 과학에서 주어진 집합의 모든 부분 집합을 찾는 것은 고전적인 문제입니다. 문제는 다음과 같습니다.

문제:

n개의 요소가 있는 집합의 가능한 모든 부분 집합을 어떻게 결정합니까?

해결책:

이 문제에 대한 간단한 접근 방식은 재귀에 있습니다. 이 개념은 다음 아이디어를 중심으로 전개됩니다.

• n=1인 경우 하위 집합은 {{}, {1}}입니다.
• n>1인 경우 다음의 하위 집합을 나눌 수 있습니다. 1,...,n-1을 n을 포함하는 그룹과 n을 포함하지 않는 그룹의 두 그룹으로 나눕니다. 이러한 그룹을 결합하면 1,...,n에 대한 하위 집합이 생성됩니다.

예:

n=5를 고려하세요.

1. 1,...,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. 사본을 만들고 각 하위 집합에 5를 추가합니다: {{5}, {1, 5}, {2, 5}, {3, 5} , {4, 5}, {1, 2, 5}, {1, 3, 5}, {1, 4, 5}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}}
3. 원래 집합과 수정된 집합의 합집합: {{}, {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}}

C 구현:

#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    if (nums.empty()) return {{}};

    vector<vector<int>> prev = subsets(vector<int>(nums.begin(), nums.end() - 1));
    vector<vector<int>> curr;

    for (auto& subset : prev) {
        curr.push_back(subset);
        subset.push_back(nums.back());
        curr.push_back(subset);
    }

    return curr;
}

위 내용은 재귀적 접근 방식을 사용하여 n개의 요소가 포함된 집합의 가능한 모든 하위 집합을 어떻게 찾을 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!