recursive

프로그래밍 대회에서 배우는 알고리즘1

chapter 6. 무식하게 풀기

6.2 재귀호출과 완전탐색

- 중첩 반복문 대체하기

- 완전탐색의 시간 복잡도:

완전탐색은 존재하는 모든 답을 하나씩 검사하므로 걸리는 시간은 가능한 답의 수에 비례한다.

해당문제의 경우는 길이 n과 선택해야하는 갯수 toPick을 입력으로 받는 경우이므로 nCtoPick, n combination toPick 만큼의 시간이 걸린다.

 

// 오름차순으로 print하는 방법생각해보기
 
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void recursion(int n, int toPick, vector<int>& picked);
void printPicked(vector<int> picked);
int main() {
    int n;    //숫자열의 길이
    int toPick;    //집합의 크기. 즉, 선택해야 하는 숫자의 갯수
    cin >> n;
    cin >> toPick;
 
    vector<int> picked;
    recursion(n,toPick, picked);
 
}
// 
void recursion(int n,int toPick, vector<int>& picked) {
    //base case
    if (toPick == 0) {    
        printPicked(picked);
        return;
    }
 
    //    처음 recursion함수가 호출 됐을 때, next = 0으로 하기위해.
    int next = picked.empty() ? 0 : picked.back() + 1;
 
    // 아직 base에 도달 못했는데, i가 n 바로 직전이면 자연스럽게 picked pop해서 해당 정답은 지워질거임
    for (int i = next; i < n; i++) {    
        picked.push_back(i);
        recursion(n, toPick - 1, picked);
        picked.pop_back();
    }
}
void printPicked(vector<int> picked) {
    sort(picked.begin(), picked.end());    // 이 코드를 추가해도 정렬이 안되누..
    while (!picked.empty()) {
        
        cout << picked.back() << " ";
        picked.pop_back();
    }
    cout << endl;
}