C++) 백준 15650번 - N과 M(2)

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

백트래킹 알고리즘을 이용해 해결할 수 있다. 조건에 따라 수를 하나씩 선택해 arr에 넣어주고 출력한다.

 

#include <bits/stdc++.h>
using namespace std;

int n,m;
int arr[10]; //수열 저장
bool used[10]; //수의 사용 여부 저장
void func(int k){ //k는 선택한 수의 개수
    if(k==m){ //m개만큼 수를 선택==arr에 삽입 했다면 출력 후 함수 종료
        for(int i=0;i<m;i++){
            cout<<arr[i]<<" ";
        }
        cout<<"\n";
        return;
    }
    for(int i=1;i<=n;i++){
        if(used[i]) continue; //이미 사용된 수 제외함
        if(k!=0&&arr[k-1]>=i) continue; //오름차순 정렬, 이전에 선택한 수보다 작은 값은 제외함
        arr[k]=i; used[i]=1;
        func(k+1); //
        used[i]=0;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin>>n>>m;
    func(0);
    
    return 0;
}