15652 N과 M (4)

문제를 이렇게 날로 먹어도 될까

 

#include <iostream>
#include <vector>

using namespace std;

void    print_vector(int m, vector<int> v)
{
    for (int i = 0; i < m; i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

bool    promising(int index, vector<int> v)
{
    for (int i = 1; i <= index; i++)
    {
        if (v[i - 1] > v[i])
            return (false);
    }
    return (true);
}

void    find_sequence(int index, int n, int m, vector<int> v)
{
    if (index == m)
        print_vector(m, v);
    else
    {
        for (int i = 1; i <= n; )
        {
            v[index] = i++;
            if (!promising(index, v))
            {
                continue;
            }
            find_sequence(index + 1, n, m, v);
        }
    }
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v(m, 0);
    
    find_sequence(0, n, m, v);
}

 

---

nm (2)에서 푼 오름차순 문제 응용해서 다시 풀었다. 중복만 가능하게 하면 돼서 중복 체크하는 부분을 없앴다. 

#include <iostream>
#include <vector>

using namespace std;

bool    visited[10];
vector  <int> v;

void    select(int n, int k, int start)
{
    if (k == 0)
    {
        for (auto& s : v)
        {
            printf("%d ", s);
        }
        printf("\n");
        return ;
    }
    for (int i = start; i <= n; i++)
    {
        visited[i] = true;
        v.push_back(i);

        select(n, k - 1, i);

        v.pop_back();
    }
}

int     main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    select(n, m, 1);
    return (0);
}