[C++] 백준 15663번 N과 M (9)

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

풀이

입력받는 수에서 중복을 제거하지 않아야 하지만, 출력하는 수열은 중복이면 안 된다.

중복 없이 수열을 출력하는 부분이 어려웠다.

현재 만들고자 하는 수열이 이미 만들어졌던 것인지 확인하는 방법은
직전 수열의 마지막 요소(last)가 현재 내가 넣고자 하는 요소와 같은지 비교하는 것이다.

백트래킹 방법을 이용하므로 새로운 수열을 만드는 것은
이미 결정된 수열 A (길이 m-1)에 x를 추가하는 것이다.
즉, x = {x1, x2, ... }에 대하여 (A + x1) 수열을 만들고, 다음 단계에서 (A + x2) 수열을 만든다.

이때, x1 == x2 이면 (A + x2) 수열은 생성하면 안 된다.
따라서 직전에 만든 수열의 마지막 숫자와, 수열의 마지막 자리에 새로 넣고자 하는 숫자가 달라야 한다.

코드

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

int n, m;
vector<int> num;
vector<bool> is_used;
vector<int> ans;

void backtracking(int cnt) {
    if(cnt == m) {
        for(int a : ans) {
            cout << a << " ";
        }
        cout << "\n";
        return;
    }
    
    int last = 0;
    
    for(int i=0; i<n; i++) {
        if(is_used[i] || num[i] == last) continue;
        
        ans[cnt] = num[i];
        last = ans[cnt];
        
        is_used[i] = true;
        backtracking(cnt + 1);
        is_used[i] = false;
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    num.resize(n);
    is_used.resize(n, false);
    ans.resize(m);
    
    for(int i=0; i<n; i++){
        cin >> num[i];
    }
    
    sort(num.begin(), num.end());
    backtracking(0);
    
    return 0;
}