[백준] 15656번 N과 M (7) (C++) - backtracking

문제

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

15656번: N과 M (7)

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<int> v;
int arr[9];

void dfs(int cnt){
  if(cnt == m){
    for(int i=0; i<m; i++){
      cout << arr[i]<< ' ';
    }
    cout << '\n';
    return;
  }
  for(int i=0; i<n; i++){
    arr[cnt] = v[i];
    dfs(cnt+1);
  }
}

int main(){
  cin >> n >> m;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(), v.end());
  dfs(0);
  return 0;
}

정리

이 문제와 15651번의 차이점은 15651번은 수열 원소의 범위를 1부터 N까지 범위를 지정한 반면 이 문제는 서로 다른 원소 N개를 입력받는다. 즉 15651번 코드에서 N개의 원소들을 입력받고 오름차순으로 정렬해주는 코드를 작성하면 해결할 수 있다.

참조

https://kdongree.tistory.com/82