[백준 15663번] [Backtracking / Map] N과 M (10)

Approach

기본적인 접근 방법은 다음 문제와 비슷하다. https://viyoung.tistory.com/286

[백준 15663번] [Backtracking / Map] N과 M (9)

다만, 비내림차순이라는 조건때문에 함수 내부의 반복문에서 자신의 index 이상부터만 고려해준다는 점에서 차이점이 존재한다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
map<int, int> cap;
int result[8];
vector<int> s;
vector<vector<int> > output;
int n, m;

void solve(int index, int cur)
{
    result[cur++] = s[index];
    cap[s[index]] -= 1;
    if (cur == m)
    {
        vector<int> temp;
        for (int i = 0; i < m; i++)
        {
            temp.push_back(result[i]);
        }
        output.push_back(temp);
    }
    else
    {
        for (int i = index; i < s.size(); i++)
        {
            if (cap[s[i]] > 0)
            {
                solve(i, cur);
            }
        }
    }
    cap[s[index]] += 1;

    return;
}

int main(void)
{
    fastio;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        cap[t] += 1;
        s.push_back(t);
    }

    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end()); // 중복 제거

    for (int i = 0; i < n; i++)
    {
        solve(i, 0);
    }
    sort(output.begin(), output.end());
    output.erase(unique(output.begin(), output.end()), output.end());
    for (int i = 0; i < output.size(); i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << output[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}