Сочетания. Необходимо получить все возможные сочетания чисел от 1до K, которые имеют длину N

Необходимо получить все возможные сочетания чисел от 1до K, которые имеют длину N

(в последовательности могут быть одинаковые элементы). Для решения задачи выделим в памяти массив A[N]. Представим себе, что все его первые qэлементов (с номерами от 0до q-1) уже определены, и надо найти все сочетания, при которых эти элементы не меняются.

Сначала ставим на место элемент с номером q. По условию на этом месте может стоять

любое число от 1до K, поэтому сначала ставим 1и находим все варианты, при которых q+1

элементов уже поставлены (здесь будет рекурсивный вызов), затем ставим на это место 2и т.д.

Если q=N, то все элементы уже поставлены на место, и надо печатать массив –одна из нужных

комбинаций готова. Ниже приведена рекурсивная процедура, которая использует массив A[N]

и печатает все комбинации на экране.

void Combinations ( int A[], int N, int K, int q )

{

if ( q == N ) // одна комбинация получена

PrintData ( A, N );

Else

for (int i = 1; i <= K; i ++ ) {

A[q] = i;

Combinations(A, N, K, q+1); // рекурсивныйвызов

}

}

Для вывода массива на экран используется такая процедура:

void PrintData ( int Data[], int N )

{

for (int i = 0; i < N; i++ )

printf("%2d ", Data[i]);

printf("\n");

}

В основной программе надо вызвать процедуру с параметром q = 0, поскольку ни один элемент

еще не установлен:

#include <stdio.h>

// здесь надо разместить процедуры

Main()

{

int A[5], N = 5, K = 10;