Комбинации k из 1 ... n в лексикографическом порядке, алгоритм слишком медленный

Question

Ниже приведен метод (с использованием обратного отслеживания) для перечисления всех возможных комбинаций в лексикографическом порядке k чисел из интервала [1, n]. Дубликаты не допускаются.
т.е.:

ввод:

5 3

вывод:

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Я хотел бы построить последовательности увеличиваются: как только я установлю первый элемент массива в 1, мне нужно будет только выполнить итерацию от 2 до e_m - (n - 2) для второго элемента; и как только этот последний достигнет 3, то третий элемент перейдет только от 4 до e_m - (n - 3) и т. д. c. Я не знаю, как это сделать, не могли бы вы помочь, пожалуйста? Метод ниже строит все последовательности из n чисел ≤ el_maxim, а затем отображает только те, которые увеличиваются. Онлайн-компилятор не примет это, потому что он слишком медленный

#include <iostream>
using namespace std;
int sol[20], n , el_maxim;
void display()
{
    for (int i = 0; i < n; i++)
        cout << sol[i] << " ";
    cout << endl;
}
int okay()
{
    for (int i = 0; i < n - 1; i++)
        if (sol[i] >= sol[i + 1])
            return 0;
    return 1;
}
void bkt(int poz)
{
    if (poz == n)
    {
        okay();
        if (okay() == 1)
            display();
    }
    else
        for (int i = 1; i <= el_maxim; i++)
        {
            sol[poz] = i;
            bkt(poz + 1);
        }
}
int main()
{
    cin >> el_maxim >> n;
    bkt(0);
    return 0;
}

Answer 1

Достаточно простого исчерпывающего поиска. Также мы можем сделать это в O(K) дополнительном пространстве, если массивы не нужны в будущем.

#include <iostream>
#include <vector>

using namespace std;

void foo(vector<int>& sol, int N, int K, int n = 1, int k = 1)
{
    if (k > K)
    {
        for (int e : sol)
            cout << e << ' ';
        cout << endl;
        return;
    }

    for (int i = n; i <= N; ++i)
    {
        sol.push_back(i);
        foo(sol, N, K, i + 1, k + 1);
        sol.pop_back();
    }
}

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> sol;
    foo(sol, N, K);
}

Answer 2

Вот некоторый рабочий код. Идея состоит в том, чтобы запомнить последний элемент, который вы использовали, чтобы не пытаться использовать его снова. Вы можете запомнить переменные между вызовами функций, используя параметры.

Чтобы сделать это быстрее, вы можете удалить функцию okay() и всегда вызывать display(), когда достигнете pos == n, потому что гарантированно, что когда вы достигнете ее, вы иметь правильный ответ. Я сделал это в своем коде.

#include <iostream>

using namespace std;
int sol[20], n , el_maxim;
void display()
{
    for (int i = 0; i < n; i++)
        cout << sol[i] << " ";
    cout << endl;
}
void bkt(int poz, int last_element)
{
    if (poz == n)
    {
         display();
    }
    else{
        for (int i = last_element + 1; i <= el_maxim; i++)
        {
            sol[poz] = i;
            bkt(poz + 1, i);
        }
    }
}
int main()
{
    cin >> el_maxim >> n;
    bkt(0, 0);
    return 0;
}