백준 15650 N과 M (2)

문제링크 : https://www.acmicpc.net/problem/15650

아이디어

• 백트래킹 - 조합 : 백트래킹 리스트 중 마지막것 다음부터 순회하며 백트래킹 수행

시간복잡도 계산

• 10^N : 1e8 > 가능

자료구조

• 백트래킹 리스트 : vector
  • 최대값 : 8이하의수 > INT 가능

코드(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int N,M;
vector<int> v;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    //리스트 중 마지막것 다음부터 순회하며 백트래킹 수행
    int last = 0;
    if(!v.empty()) last = v.back();
    
    for(int i=last+1; i<=N; i++) {
        v.push_back(i);
        dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
    dfs();
    return 0;
}
 

문제유형

• 백트래킹 - 순열, 조합
  • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
  • 조합 : 리스트 마지막 다음부터 순회
  • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

• https://www.acmicpc.net/problem/15649
• https://www.acmicpc.net/problem/15650
• https://www.acmicpc.net/problem/15651
• https://www.acmicpc.net/problem/15652
• https://www.acmicpc.net/problem/15663