Все сочетания из n по k

Question

Моё решение не проходит по времени эту задачу https://informatics.msk.ru/mod/statements/view.php?id=211&chapterid=87#1 Не знаю, как его оптимизировать.

Вот код:

#include <iostream>
using namespace std;
short int k,n;
short int a[101];
void f(short int i){
    if(i==k+1){   
        for(short int j = 1;j <= k;j++)cout<<a[j]<<" ";
        cout<<"\n";
    }
    else{
        for(int j = a[i-1]+1;j <= n;j++){
            a[i]=j;
            f(i+1);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    f(1);
return 0;
}

Answer 1

Сложность того что вы написали экспоненциальная. Попробуйте запускать вашу программу с n = k. При увеличении обоих параметров на единицу время исполнения растёт в два раза:

 n    k   время
27   27   0.781 c
28   28   1.419 c
29   29   2.923 c
30   30   5.710 c

Почему - я не разбирался. Выглядит будто вы перебираете заведомо нерабочие комбинации. Например когда n = k бесполезно перебирать комбинации в которых на первом месте что-то кроме единицы.

Улучшить ситуацию можно такой правкой:

11c11
<         for(int j = a[i-1]+1;j <= n;j++){
---
>         for(int j = a[i-1]+1;j <= n-(k-i); j++){

j теперь никогда не принимает значений при которых рекурсия зайдёт в тупик.

Другой способ

Ту же задачу можно сделать без рекурсии. Функция next ищет следующую комбинацию:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

bool next(std::vector<int> &a, int n) {
    const int k = a.size();
    for (int i = k - 1; i >= 0; --i) {
        const int b = a[i] - i;
        if (b <= n - k) {
            for (int j = i; j < k; ++j) {
                a[j] = b + j + 1;
            }
            return true;
        }
    }
    return false;
}

void print(const std::vector<int> &a) {
    std::copy(a.begin(), a.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

void combinations(int n, int k) {
    if (k < 0 || n < k) {
        return;
    }

    std::vector<int> a(k);
    for (int i = 0; i < k; ++i) {
        a[i] = i + 1;
    }
    print(a);
    while (next(a, n)) {
        print(a);
    }
}

int main() {
    int n;
    int k;
    if (!(std::cin >> n >> k)) {
        return 1;
    }
    combinations(n, k);
}

БЛОГ НА HUSL

Все сочетания из n по k

Ответы (1 шт):

Другой способ