A multicombination is a combination that can contain duplicates (i.e., the combination is a multiset).

Note that the source set does not contain duplicates. For combinations of a set that contains duplicates, see combinations of a multiset.

These are the 3-multicombinations of the 4-set {0, 1, 2, 3}:

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 0, 3]
[0, 1, 1]
[0, 1, 2]
[0, 1, 3]
[0, 2, 2]
[0, 2, 3]
[0, 3, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 2, 3]
[1, 3, 3]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 3]

This algorithm produces the combinations in lexicographic order, with the elements in each combination in increasing order.

To find the next multicombination containing k elements from a set containing n elements, begin with the multicombination containing k zeroes, then at each step:

1. Find the rightmost element that is less than n – 1
2. Increment it.
3. Make the elements after it the same.

unsigned int next_multicombination(unsigned int *ar, size_t n, unsigned int k)
{
	unsigned int changed = 0;
	int i;

	for (i = k - 1; i >= 0 && !changed; i--) {
		if (ar[i] < n - 1) {
			/* Increment this element */
			ar[i]++;
			if (i < k - 1) {
				/* Make the elements after it the same */
				unsigned int j;
				for (j = i + 1; j < k; j++) {
					ar[j] = ar[j - 1];
				}
			}
			changed = 1;
		}
	}
	if (!changed) {
		/* Reset to first combination */
		for (i = 0; i < k; i++) {
			ar[i] = 0;
		}
	}
	return changed;
}

Example program to produce the output above:

void print_array(const unsigned int *ar, size_t len, FILE *fptr)
{
	unsigned int i;
	fputc('[', fptr);
	for (i = 0; i < len; i++) {
		fprintf(fptr, "%d", ar[i]);
		if (i < len - 1) {
			fputs(", ", fptr);
		}
	}
	fputc(']', fptr);
}

int main(void)
{
	unsigned int numbers[3] = {0};
	const size_t k = sizeof(numbers) / sizeof(numbers[0]);
	unsigned int n = 4;

	do {
		print_array(numbers, k, stdout);
		putchar('\n');
	} while (next_multicombination(numbers, n, k));

	return 0;
}