백준 부분집합의 합 풀이 접근 하기

아래 문제는 부분 집합들의 합을 구하는 문제로 

부분 집합을 구하는게 기본 틀인 문제이다.

수업떄 따로 배운 내용으로는 2^N 의 Y,N 으로 이뤄진 각각의 tree 를 구현하는것이 관건이다..

결과부터 말하자면 아래 처럼 이뤄지는데  이게 결국은 부분 집합의 값들이 되게 된다 .

즉 00001 00010 00011 이런식으로 이뤄 지게 되고 각각의 1이 가르키는 것은 입력값들을 부분 집합으로 만들어 주는 역활을 한다. 

YYYYY 

YYYYN 

YYYNY 

이상 끝 !! 

 

#include <iostream> #include <vector> using namespace std; int N = 6; void print_vector(vector<char>& v) { for(int i=0; i<v.size(); i++) { cout << v[i] << " "; } cout << endl; } void recursive(vector<char>& v) { if(v.size() == N) { print_vector(v); return; } v.push_back('Y'); recursive(v); v.pop_back(); v.push_back('N'); recursive(v); v.pop_back(); } int main() { // cin >> N; vector<char> temp; recursive(temp); return 0; }

www.acmicpc.net/problem/1182