N과 M (9) 15663

문제

접근 방법

이전 N과 M 문제보다는 약간 까다로워졌다.
중복된 수는 허용되지만, 중복된 수열은 허용하지 않는 것이다.

여러 방법이 있겠지만 이전에 사용한 숫자인 경우 건너뛰는 방식으로 해결하면 된다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, arr[8], ret[8], cnt[10001];
void dfs(int depth)
{
    if (depth == M)
    {
        for (int i = 0; i < M; ++i)
            cout << ret[i] << " ";
        cout << "\n";
        return;
    }
    int prev = 0;
    for (int i = 0; i < N; ++i)
    {
        if (prev != arr[i] && cnt[arr[i]])
        {
            --cnt[arr[i]];
            prev = ret[depth] = arr[i];
            dfs(depth + 1);
            ++cnt[arr[i]];
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
        ++cnt[arr[i]];
    }
    sort(arr, arr + N);
    dfs(0);
}

풀이

다른 사람의 풀이를 보니 사용한 숫자가 아닌 인덱스를 체크하는 식으로 해결하였다.
그 방법이 더욱 정답에 가까운 것 같다.