[C++] 15650번 N과 M (2) - 백트래킹

#include <iostream>
#include <vector>

using namespace std;

int N, M;  //자연수 N, 길이가 M인 수열

void f(int n, int m, vector<int> v)  //현재 숫자와 몇 개 출력했음?
{
    if(m==M) {  //다 선택했으면 출력
        for(int i=0; i<v.size(); i++)
            cout << v[i] << ' ';
        cout << '\n';
        return;
    }
    
    if(N-n+1<M-m) return;  //조건에 맞지 않으면 백트래킹
    
    v.push_back(n);
    f(n+1, m+1, v);
    v.pop_back();
    f(n+1, m, v);  //출력하지 않고+1, 출력하고 +1
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    vector<int> v; v.clear();
    f(1, 0, v);
    
    return 0;
}

딱 백트래킹 기본문제이다. 솔직히 백트래킹이라기보다는 재귀함수에 조건문 하나 넣어놓은 느낌이고 백트래킹이 필요할까 싶기는 한데... 아 그리고 나는 벡터를 넣어주는 방식으로 했는데 다른 사람의 코드를 보고 생각해보니 하나의 배열에다가 덮어씌우기 형태로 해도 될 것 같다. 왜냐함녀 이게 백트래킹이 DFS방식이다보니까 겹칠일이 없기 때문이다. 암튼 그렇다구...

 

<C++ vector>

https://hwan-shell.tistory.com/119

C++ vector사용법 및 설명 (장&단점)

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.