[백준 15655번] N과 M (6) (C++)

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

15655번: N과 M (6)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M, arr[9];
vector<int>v;

void func(int cnt, int idx)
{
    if(cnt==M)
    {
        for(int i=0; i<M; i++) cout << v[i] << " ";
        cout << "\n";
        return;
    }
    else
    {
        for(int i=idx; i<N; i++) //백트래킹
        {
            v.push_back(arr[i]); 
            func(cnt+1, i+1); //카운팅, 인덱스 증가
            v.pop_back();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N); //사전 순으로 증가하는 순서로 정렬
    func(0, 0);

    return 0;
}

 

간단한 백트래킹 문제이다.

사전 순으로 증가하는 순서로 출력하도록 되어있기 때문에, 입력받은 배열에 오름차순 정렬을 먼저 해주어야 한다.

 

다음 현재 인덱스를 기준으로 값을 넣고, 다음 재귀로 카운팅 + 1 및 현재 인덱스 기준 + 1을 넘겨준다.

다음으로 넣었던 값을 다시 삭제하여 다른 값으로 탐색을 이어나간다.

 

재귀를 통해 카운팅을 넘겨주면서 해당 카운팅이 M과 같아질 때 인덱스를 기준으로 담았던 값들을 출력해주면 된다.