[백준 15654번] [Backtracking] N과 M (5)

Approach

수열이 무작위로 주어지는 상황이므로 정렬을 하고, 어느 인덱스까지 사용했는지를 확인해주고 넣어주면 된다.

인덱스를 키워나가면서 계속 채우는 상황이므로 함수의 parameter에는 채우고 있는 index만 있으면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
vector<int> v;
int N, M;
int visited[8];
int result[8];

void solve(int index){
    if(index == M){
        for(int i = 0; i < M; i++){
            if(i != M - 1) cout << result[i] << " ";
            else cout << result[i] << "\n";
        }
        return;
    }
    else{
        for(int i = 0; i < N; i++){
            if(visited[i]) continue;
            visited[i] = 1;
            result[index] = v[i];
            solve(index + 1);
            visited[i] = 0;
        }
        return;
    }
}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(result, 0, sizeof(result));
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        int t;
        cin >> t;
        v.push_back(t);
    }

    sort(v.begin(), v.end());
    solve(0);
}