fork(106) download
  1. // Program to print all combination of size r in an array of size n
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. void combinationUtil(int arr[], int data[], int start, int end, int index, int r);
  5.  
  6. // Needed for qsort. See http://w...content-available-to-author-only...s.com/reference/cstdlib/qsort/
  7. int compare (const void * a, const void * b)
  8. { return ( *(int*)a - *(int*)b ); }
  9.  
  10. // The main function that prints all combinations of size r
  11. // in arr[] of size n. This function mainly uses combinationUtil()
  12. void printCombination(int arr[], int n, int r)
  13. {
  14. // A temporary array to store all combination one by one
  15. int data[r];
  16.  
  17. // Sort array to handle duplicates
  18. qsort (arr, n, sizeof(int), compare);
  19.  
  20. // Print all combination using temprary array 'data[]'
  21. combinationUtil(arr, data, 0, n-1, 0, r);
  22. }
  23.  
  24. /* arr[] ---> Input Array
  25.   data[] ---> Temporary array to store current combination
  26.   start & end ---> Staring and Ending indexes in arr[]
  27.   index ---> Current index in data[]
  28.   r ---> Size of a combination to be printed */
  29. void combinationUtil(int arr[], int data[], int start, int end, int index, int r)
  30. {
  31. // Current combination is ready to be printed, print it
  32. if (index == r)
  33. {
  34. for (int i=0; i<r; i++)
  35. printf("%d " ,data[i]);
  36. printf("\n");
  37. return;
  38. }
  39.  
  40. // replace index with all possible elements. The condition
  41. // "end-i+1 >= r-index" makes sure that including one element
  42. // at index will make a combination with remaining elements
  43. // at remaining positions
  44. for (int i=start; i<=end && end-i+1 >= r-index; i++)
  45. {
  46. data[index] = arr[i];
  47. combinationUtil(arr, data, i+1, end, index+1, r);
  48.  
  49.  
  50. // Remove duplicates
  51. while (arr[i] == arr[i+1])
  52. i++;
  53. }
  54. }
  55.  
  56. // Driver program to test above functions
  57. int main()
  58. {
  59. int arr[] = {1, 2, 1, 3, 1};
  60. int r = 3;
  61. int n = sizeof(arr)/sizeof(arr[0]);
  62. printCombination(arr, n, r);
  63. }
  64.  
Success #stdin #stdout 0s 2852KB
stdin
Standard input is empty
stdout
1 1 1 
1 1 2 
1 1 3 
1 2 3