2
\$\begingroup\$

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 <stdio.h>
#include <stdlib.h>
#include <time.h>

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

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

    for(i=start; i<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", &n, &k);

    // 1<=n<=100 ; 1<=k<=n
    if(n>100||n<1 && k>n||k<1)
        return 0;

    int i;
    for(i=0; i<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.

\$\endgroup\$
2
  • \$\begingroup\$ Are you sure 100, 95 is a reasonable input? According to my calculations, you would need to output roughly 450GB in one second. Math: \${{100}\choose{95}} * 95 * 4 = 452979912000\$, where \${100}\choose{95}\$ is the number of sets, 95 is the number of elements in each set, and 4 is the number of characters per element (2 digits plus comma plus space). Even 50, 48 would require outputting 3.7 MB in one second, which may be difficult. \$\endgroup\$
    – JS1
    Mar 30 '18 at 11:02
  • \$\begingroup\$ @JS1 I don't really know about the size of how much it takes. But yeah, it is possible through some other code because some people solved it. \$\endgroup\$
    – Roy Yoon
    Mar 31 '18 at 0:21
2
\$\begingroup\$

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} -> {1, 2, 3} {1, 2, 4} {1, 2, 5}
{1, 3} -> {1, 3, 4} {1, 3, 5}
{1, 4} -> {1, 4, 5}
{1, 5} -> 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.

\$\endgroup\$
1
\$\begingroup\$
        for(j=0; j<k; j++){
            if(j==k-1)
                printf("%d\n", pos[j]);
            else{
                printf("%d ", pos[j]);
            }
        }

KISS:

        for(j=0; j<k; j++){
            printf("%d ", pos[j]);
        }
        printf("\n");

I am not sure about if there is another way that doesn't use recursion.

There is. If I give you a subset, how do you find the next one?

If the last element of the subset is not the last element in An then increment it and return. Otherwise, if the element to its left is not the penultimate element in An, increment that one and extend to the right. Otherwise, ...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.