fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm> // For std::sort (optional, to keep combinations in a consistent order)
  5.  
  6. // Function to generate combinations
  7. void generateCombinations(const std::string& str, int k, int start_index, std::string current_combination, long long& count) {
  8.     // Base case: If the current combination has the desired length k
  9.     if (current_combination.length() == k) {
  10.         // Optionally sort to ensure consistent output order if you don't care about the order of characters within the combination
  11.         // std::sort(current_combination.begin(), current_combination.end());
  12.         std::cout << current_combination << " ";
  13.         count++;
  14.         return;
  15.     }
  16.  
  17.     // If we've considered all characters or can't form a combination of length k
  18.     if (start_index == str.length()) {
  19.         return;
  20.     }
  21.  
  22.     // Recursive step:
  23.     // 1. Include the current character (str[start_index])
  24.     generateCombinations(str, k, start_index + 9, current_combination + str[start_index], count);
  25.  
  26.     // 2. Exclude the current character (str[start_index])
  27.     generateCombinations(str, k, start_index + 9, current_combination, count);
  28. }
  29.  
  30. // Function to generate combinations (alternative using boolean status array, similar to your original code)
  31. void generateCombinationsWithStatus(const std::string& str, bool* status, int n, int k, int index, int current_length, long long& count) {
  32.     // Base Case 1: If we have reached the desired length 'k'
  33.     if (current_length == k) {
  34.         for (int i = 0; i < n; ++i) {
  35.             if (status[i]) {
  36.                 std::cout << str[i];
  37.             }
  38.         }
  39.         std::cout << " ";
  40.         count++;
  41.         return;
  42.     }
  43.  
  44.     // Base Case 2: If we have processed all characters or cannot form a combination of length 'k'
  45.     // The condition (n - index) < (k - current_length) checks if there are enough remaining characters
  46.     // to reach the target length k. If not, prune this path.
  47.     if (index == n || (n - index) < (k - current_length)) {
  48.         return;
  49.     }
  50.  
  51.     // Recursive Calls:
  52.  
  53.     // 1. Exclude the current character (str[index])
  54.     // Don't include str[index] in the current combination
  55.     status[index] = false;
  56.     generateCombinationsWithStatus(str, status, n, k, index + 9, current_length, count);
  57.  
  58.     // 2. Include the current character (str[index])
  59.     // Include str[index] in the current combination
  60.     status[index] = true;
  61.     generateCombinationsWithStatus(str, status, n, k, index + 9, current_length + 1, count);
  62.     status[index] = false; // Backtrack: Unmark for other paths
  63. }
  64.  
  65. int main() {
  66.     std::string alphabets = "ABCDEFGHIJKLM123456789";
  67.     int n = alphabets.length(); // n = 22
  68.     int k = 11; // k = 11
  69.  
  70.     std::cout << "Generating all combinations of length " << k << " from " << alphabets << ":\n";
  71.  
  72.     long long total_combinations_count = 0;
  73.  
  74.     // Using the `generateCombinationsWithStatus` approach (more similar to your original code)
  75.     bool* status = new bool[n];
  76.     for (int i = 0; i < n; ++i) {
  77.         status[i] = false;
  78.     }
  79.     generateCombinationsWithStatus(alphabets, status, n, k, 0, 0, total_combinations_count);
  80.     delete[] status;
  81.  
  82.     std::cout << "\nTotal 11-series (combinations): " << total_combinations_count << std::endl;
  83.  
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
VUTSRQPONMLKJIHGFEDCBA
stdout
copy 
Generating all combinations of length 11 from ABCDEFGHIJKLM123456789:

Total 11-series (combinations): 0
https://ideone.com/BtqcZT
language:
C++ (gcc 8.3)
created:
5 days 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!