fork(147) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1 1 
1 1 2 
1 1 3 
1 2 3
https://ideone.com/ywsqBz
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!