Question

How to represent the number of different ways in which n can be separated with stars in C++

Answer 1

#include <iostream>

long long ways(int n) {
    if (n <= 0) return 0;

    return 1LL << (n - 1); // 2^(n-1)
}

void printSeparations(int n) {
    int gaps = n - 1;
    int total = 1 << gaps; // 2^(n-1)

    for (int mask = 0; mask < total; mask++) {
        // print first coin
        std::cout << "*";
        // decide for each gap whether to put a separator
        for (int i = 0; i < gaps; ++i) {
            if (mask & (1 << i))
                std::cout << " | "; // separator between groups
            else
                std::cout << " ";   // same group
            std::cout << "*";
        }
        std::cout << "\n";
    }
}

int main() {
    int n = 5;
    
    std::cout << "Number of ways: " << ways(n) << "\n";
    
    if (ways(n)) printSeparations(n);
}

 
 
/*
run:
 
Number of ways: 16
* * * * *
* | * * * *
* * | * * *
* | * | * * *
* * * | * *
* | * * | * *
* * | * | * *
* | * | * | * *
* * * * | *
* | * * * | *
* * | * * | *
* | * | * * | *
* * * | * | *
* | * * | * | *
* * | * | * | *
* | * | * | * | *
 
*/

 

70+ SQL courses for beginners and professionals