알고리즘 트레이닝 – 재귀(Recursion)적 알고리즘

원소가 n 개인 집합의 모든 부분집합을 생성하는 재귀적 알고리즘

#include <vector>

using namespace std;

class Subset
{
public:
    Subset();
    vector<int> subset;
    void search(int k);
}

Subset::Subset()
{
    search(1);
}

Subset::search(int k)
{
    int n = 3;
    if (k == n+1)
    {
        // 부분집합을 처리한다.
    }
    else
    {
        // k를 부분집합에 포함시킨다.
        subset.push_back(k);
        search(k+1);

        // k를 부분집합에 포함시키지 않는다.
        subset.pop_back();
        search(k+1);
    }
}

int main()
{
    Subset subset = Subset();
}

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중

This site uses Akismet to reduce spam. Learn how your comment data is processed.