Find subsets of size K in N set The question is: There is a set An, and it consists of integers from 1 to n.

An={1, 2, 3, ..., n}

Print all subsets of size K in An. It must be generated in order like the example below.

So for example, n=5 k=3

{1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} ... {3, 4, 5}

I am not sure about if there is another way that doesn't use recursion. I did this with recursion but the problem is that all test cases should be done within 1 sec. When N and K are like 5, 3 and 12, 6 it is okay but when it comes to like 50, 48 or 100, 95, it takes too long. I am having a real struggle with this problem.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;

void subset(int n, int k, int arr[], int pos[], int index, int start){
    int i, j;

    if(index == k){
        for(j=0; j&lt;k; j++){
            if(j==k-1)
                printf("%d\n", pos[j]);
            else{
                printf("%d ", pos[j]);
            }
        }
        return;
    }

    for(i=start; i&lt;n; i++){
        pos[index] = arr[i]; 
        subset(n, k, arr, pos, index+1, i+1);
    }
}

int main(){
    int n, k, arr[100], index=0, start=0;

    scanf("%d %d", &amp;n, &amp;k);

    // 1&lt;=n&lt;=100 ; 1&lt;=k&lt;=n
    if(n&gt;100||n&lt;1 &amp;&amp; k&gt;n||k&lt;1)
        return 0;

    int i;
    for(i=0; i&lt;n; i++)
        arr[i]=i+1;

    int *pos = (int*)malloc(sizeof(int)*k);

    time_t clockstart=0, clockend=0;
    float gap;
    clockstart = clock();
    subset(n, k, arr, pos, index, start);
    clockend = clock();
    gap = (float)(clockend-clockstart)/(CLOCKS_PER_SEC);

    printf("%f\n", gap);

    return 0;
}


I think i should use something like tail recursion or vector in C++ but I can't figure out how to work with those.
As you probably noticed, the slowdown happens when n is large and k is close to n. If it is slower than it should be, it is likely because it is doing unnecessary work. Lets have a look at the case where n=5 and k=3, and go to the point in the execution of your program where arr[0] = 1 and index = 1. In the for-loop in subset(), you are looking at all possible values from start = 2 to n = 5. However, not all values will actually result in valid solutions. Here is a list of all {1, i} you check, and which subsets are possible:

{1, 2} -&gt; {1, 2, 3} {1, 2, 4} {1, 2, 5}
{1, 3} -&gt; {1, 3, 4} {1, 3, 5}
{1, 4} -&gt; {1, 4, 5}
{1, 5} -&gt; no solutions


As you can see, {1, 5} does not have any possible subsets. Or put otherwise, 5 is too large a number at pos[1] to give any solutions.

Instead of trying all numbers from start to n, try to find out what the actual maximum is that will still give solutions.