0

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;
}
Penny Liu
  • 15,447
  • 5
  • 79
  • 98
nultype
  • 21
  • 5
  • 1
    `okay();if (okay() == 1)` -- Why are you calling `okay` twice? – PaulMcKenzie Apr 27 '20 at 15:07
  • Does this answer your question? [Algorithm to return all combinations of k elements from n](https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) There you'll get to see many algorithms which are more effective in terms of what you are doing here. – brc-dd Apr 27 '20 at 15:19
  • because I am a dummy and I had some errors when I tried to check the if statement alone, fixed some things in the code and I thought that calling the function beforehand is the way to do it sice I didn t have bugs anymore – nultype Apr 27 '20 at 15:21
  • @nultype "OOP in Java and I want to work on a website" you mean JavaScript? Or are Java and working on the website two different things. I just don't want you starting to learn Java with the intention of using it to develop websites. You CAN use Java for websites. You can use anything for a backend, but something like JavaScript using Node.js or Python using Django are more common. – JohnFilleau Apr 27 '20 at 15:36
  • two different things, mate. Haha, I am a noob but not on the level of using Java for web ^^ – nultype Apr 27 '20 at 17:35
  • I currently am part of a course which teaches fundamentals in C++ (almost done), OOP in Java and some SQL and after I am done I gotta create a personal project and I have the idea already, it'll be a web app.. You can think of this course like a bootcamp, and the technologies needed for creating whatever it is I need will be studied by myself online so that'll be fun – nultype Apr 27 '20 at 17:37

2 Answers2

-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;
}
Mahmood Darwish
  • 536
  • 3
  • 12
-1

A simple exhaustive search should suffice. Also we can do it in O(K) extra space if the arrays are not needed in future.

#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);
}
srt1104
  • 959
  • 7
  • 11
  • with endl it didn't work, too slow for one of the testcases, changed it to '\n' and it's working, thanks kind stranger! – nultype Apr 27 '20 at 15:32