Combinations of k of 1...n in lexycographical order, algorithm too slow

Question

Below is a method (using backtracking) to list all possible combinations, in lexicographical order,of k numbers out of the interval [1,n].. duplicates are not allowed.
i.e:

input:

5 3

output:

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

I would like to build the sequences increasingly: once I set the first array element to 1 I'd only need to iterate from 2 to e_m - (n - 2) for the second element; and once that latter reaches 3, then the third element only goes from 4 to e_m - (n - 3), etc. I don't know how to do that tho, can you help, please? The method below builds all the sequences of n numbers ≤ el_maxim and then displays only those increasing.. The online compiler won't accept this because it is too slow

#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

Here's some working code. The idea is to remember the last element you used in order to not try to use it again. You can remember variables between function calls using parameters.

To make this faster you can delete the okay() function and always call display() when you reach pos == n because it is guaranteed that when you reach it you have a correct answer. I did that in my code.

#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;
}