// Program to print all combination of size r in an array of size n
#include <stdio.h>
#include <stdlib.h>
void combinationUtil(int arr[], int data[], int start, int end, int index, int r);
// Needed for qsort. See http://w...content-available-to-author-only...s.com/reference/cstdlib/qsort/
int compare (const void * a, const void * b)
{ return ( *(int*)a - *(int*)b ); }
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombination(int arr[], int n, int r)
{
// A temporary array to store all combination one by one
int data[r];
// Sort array to handle duplicates
qsort (arr, n, sizeof(int), compare);
// Print all combination using temprary array 'data[]'
combinationUtil(arr, data, 0, n-1, 0, r);
}
/* arr[] ---> Input Array
data[] ---> Temporary array to store current combination
start & end ---> Staring and Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
void combinationUtil(int arr[], int data[], int start, int end, int index, int r)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int i=0; i<r; i++)
printf("%d " ,data[i]);
printf("\n");
return;
}
// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a combination with remaining elements
// at remaining positions
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1, end, index+1, r);
// Remove duplicates
while (arr[i] == arr[i+1])
i++;
}
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 2, 1, 3, 1};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
}
Ly8gUHJvZ3JhbSB0byBwcmludCBhbGwgY29tYmluYXRpb24gb2Ygc2l6ZSByIGluIGFuIGFycmF5IG9mIHNpemUgbgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgp2b2lkIGNvbWJpbmF0aW9uVXRpbChpbnQgYXJyW10sIGludCBkYXRhW10sIGludCBzdGFydCwgaW50IGVuZCwgaW50IGluZGV4LCBpbnQgcik7CgovLyBOZWVkZWQgZm9yIHFzb3J0LiAgU2VlIGh0dHA6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLmNvbS9yZWZlcmVuY2UvY3N0ZGxpYi9xc29ydC8KaW50IGNvbXBhcmUgKGNvbnN0IHZvaWQgKiBhLCBjb25zdCB2b2lkICogYikKeyAgcmV0dXJuICggKihpbnQqKWEgLSAqKGludCopYiApOyAgfQoKLy8gVGhlIG1haW4gZnVuY3Rpb24gdGhhdCBwcmludHMgYWxsIGNvbWJpbmF0aW9ucyBvZiBzaXplIHIKLy8gaW4gYXJyW10gb2Ygc2l6ZSBuLiBUaGlzIGZ1bmN0aW9uIG1haW5seSB1c2VzIGNvbWJpbmF0aW9uVXRpbCgpCnZvaWQgcHJpbnRDb21iaW5hdGlvbihpbnQgYXJyW10sIGludCBuLCBpbnQgcikKewogICAgLy8gQSB0ZW1wb3JhcnkgYXJyYXkgdG8gc3RvcmUgYWxsIGNvbWJpbmF0aW9uIG9uZSBieSBvbmUKICAgIGludCBkYXRhW3JdOwoKICAgIC8vIFNvcnQgYXJyYXkgdG8gaGFuZGxlIGR1cGxpY2F0ZXMKICAgIHFzb3J0IChhcnIsIG4sIHNpemVvZihpbnQpLCBjb21wYXJlKTsKCiAgICAvLyBQcmludCBhbGwgY29tYmluYXRpb24gdXNpbmcgdGVtcHJhcnkgYXJyYXkgJ2RhdGFbXScKICAgIGNvbWJpbmF0aW9uVXRpbChhcnIsIGRhdGEsIDAsIG4tMSwgMCwgcik7Cn0KCi8qIGFycltdICAtLS0+IElucHV0IEFycmF5CiAgIGRhdGFbXSAtLS0+IFRlbXBvcmFyeSBhcnJheSB0byBzdG9yZSBjdXJyZW50IGNvbWJpbmF0aW9uCiAgIHN0YXJ0ICYgZW5kIC0tLT4gU3RhcmluZyBhbmQgRW5kaW5nIGluZGV4ZXMgaW4gYXJyW10KICAgaW5kZXggIC0tLT4gQ3VycmVudCBpbmRleCBpbiBkYXRhW10KICAgciAtLS0+IFNpemUgb2YgYSBjb21iaW5hdGlvbiB0byBiZSBwcmludGVkICovCnZvaWQgY29tYmluYXRpb25VdGlsKGludCBhcnJbXSwgaW50IGRhdGFbXSwgaW50IHN0YXJ0LCBpbnQgZW5kLCBpbnQgaW5kZXgsIGludCByKQp7CiAgICAvLyBDdXJyZW50IGNvbWJpbmF0aW9uIGlzIHJlYWR5IHRvIGJlIHByaW50ZWQsIHByaW50IGl0CiAgICBpZiAoaW5kZXggPT0gcikKICAgIHsKICAgICAgICBmb3IgKGludCBpPTA7IGk8cjsgaSsrKQogICAgICAgICAgICBwcmludGYoIiVkICIgLGRhdGFbaV0pOwogICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgLy8gcmVwbGFjZSBpbmRleCB3aXRoIGFsbCBwb3NzaWJsZSBlbGVtZW50cy4gVGhlIGNvbmRpdGlvbgogICAgLy8gImVuZC1pKzEgPj0gci1pbmRleCIgbWFrZXMgc3VyZSB0aGF0IGluY2x1ZGluZyBvbmUgZWxlbWVudAogICAgLy8gYXQgaW5kZXggd2lsbCBtYWtlIGEgY29tYmluYXRpb24gd2l0aCByZW1haW5pbmcgZWxlbWVudHMKICAgIC8vIGF0IHJlbWFpbmluZyBwb3NpdGlvbnMKICAgIGZvciAoaW50IGk9c3RhcnQ7IGk8PWVuZCAmJiBlbmQtaSsxID49IHItaW5kZXg7IGkrKykKICAgIHsKICAgICAgICBkYXRhW2luZGV4XSA9IGFycltpXTsKICAgICAgICBjb21iaW5hdGlvblV0aWwoYXJyLCBkYXRhLCBpKzEsIGVuZCwgaW5kZXgrMSwgcik7CgoKICAgICAgICAvLyBSZW1vdmUgZHVwbGljYXRlcwogICAgICAgIHdoaWxlIChhcnJbaV0gPT0gYXJyW2krMV0pCiAgICAgICAgICAgICBpKys7CiAgICB9Cn0KCi8vIERyaXZlciBwcm9ncmFtIHRvIHRlc3QgYWJvdmUgZnVuY3Rpb25zCmludCBtYWluKCkKewogICAgaW50IGFycltdID0gezEsIDIsIDEsIDMsIDF9OwogICAgaW50IHIgPSAzOwogICAgaW50IG4gPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKICAgIHByaW50Q29tYmluYXRpb24oYXJyLCBuLCByKTsKfQo=