백준 15664번: N과 M (10)

문제

문제 바로가기> 백준 15664번: N과 M (10)

풀이

재귀를 이용한 backtraking으로 문제를 풀었다. 사전 순으로 출력하기 위해 사전에 정렬을 진행했고, 중복되는 수열을 여러 번 출력하지 않기 위해 같은 cnt일 경우 이전에 고른 수는 방문하지 않았다. 또한 비내림차순 조건을 만족하기 위해 (ex 7 1과 1 7 => 1 7 한번만) from 변수를 사용해 주었다.

#include<iostream>
#include<algorithm>
using namespace std;

int n, m;
int num[9]{};
int ans[9]{};
bool visit[9]={false};

void backtracking(int from, int cnt){
    if(cnt==m){
        for(int i=0; i<m; i++) cout << ans[i] << ' ';
        cout<<'\n';
        return;
    }
    int prev_num = -1;
    for(int i=from; i<=n; i++){
        if(!visit[i] && prev_num!=num[i]){
            visit[i] = true;
            ans[cnt] = num[i];
            prev_num = num[i];
            backtracking(i+1, cnt+1);
            visit[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>num[i];
    sort(num, num+n+1);
    backtracking(1, 0);
}