[15657] N과 M(8)

내 코드

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

int field[10];
int arr[10];
int n,m;

void recursive(int k)
{
    if(k>m)
    {
        for(int i = 1;i<=m;i++)
        cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1;i<=n;i++)
    {
        if(arr[k-1] > field[i]) continue;
        arr[k] = field[i];
        recursive(k+1);
    }
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i<=n;i++)
        cin >> field[i];
    sort(field,field+n+1);
    recursive(1);
}

• k=1 부터 시작하는 배열에 arr[k-1] 값과 비교해 값을 넣는 백트래킹.

정답

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

int n, m;
int arr[10];
int num[10];

void func(int k, int st){
  if(k == m){
    for(int i = 0; i < m; i++)
      cout << num[arr[i]] << " ";
    cout << "\n";
    return;
  }

  for(int i = st; i < n; i++){
    arr[k] = i;
    func(k+1, i);
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++)
    cin >> num[i];
  sort(num, num+n);
  func(0, 0);
}

• func() 함수에서 넣을 인덱스 값의 위치뿐만 아니라 시작값까지 인자로 전달하고 있다.
• num 배열에는 arr 배열의 인덱스 값을 순서대로 저장하고 있다.