Advertisement
jasonpogi1669

Combinations with repetitions using C++

Jan 21st, 2022
671
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<vector<int>> res;
  6.  
  7. void CombinationRepetitionUtil(int chosen[], int arr[], int index, int r, int start, int end) {
  8.     if (index == r) {
  9.         vector<int> vec;
  10.         for (int i = 0; i < r; i++) {
  11.             vec.push_back(arr[chosen[i]]);
  12.         }
  13.         res.push_back(vec);
  14.         return;
  15.     }
  16.     for (int i = start; i <= end; i++) {
  17.         chosen[index] = i;
  18.         CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end);
  19.     }
  20.     return;
  21. }
  22.  
  23. void CombinationRepetition(int arr[], int n, int r) {
  24.     int chosen[r + 1];
  25.     CombinationRepetitionUtil(chosen, arr, 0, r, 0, n - 1);
  26. }
  27.  
  28. int main() {
  29.     ios::sync_with_stdio(false);
  30.     cin.tie(0);
  31.     int arr[] = {0, 1, 2, 3};
  32.     int n = sizeof(arr) / sizeof(arr[0]);
  33.     int r = 2;
  34.     // generate all combinations of size r (using the elements from the array)
  35.     CombinationRepetition(arr, n, r);
  36.     for (int i = 0; i < (int) res.size(); i++) {
  37.         for (int j = 0; j < (int) res[i].size(); j++) {
  38.             cout << res[i][j] << " ";
  39.         }
  40.         cout << '\n';
  41.     }
  42.     return 0;
  43. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement