#include <cassert>
#include <cstddef>
#include <iostream>

// Printing all subsets of a set
//
// Suppose we have the set:
//
//     {1, 2, 3}
//
// Its subsets are:
//
//     {}
//     {1}
//     {2}
//     {3}
//     {1, 2}
//     {1, 3}
//     {2, 3}
//     {1, 2, 3}
//
// There are eight subsets.
//
// The empty set is a subset of every set, and
// every set is a subset of itself.
//
// In general, a set containing n distinct
// elements has:
//
//     2^n
//
// subsets.
//
//
//
// How can we generate all of them recursively?
//
// For every element, we must make one of two
// decisions:
//
//     Include the element in the subset.
//
// or:
//
//     Exclude the element from the subset.
//
// Once we have made this decision, we can
// recursively process the remaining elements.
//
// Thus, every non-trivial recursive call makes
// TWO recursive calls, each solving a smaller
// version of the same problem.
//
//
//
// We will use a Boolean membership array.
//
// For the set:
//
//     {1, 2, 3}
//
// an array containing:
//
//     true, false, true
//
// represents:
//
//     {1, 3}.
//
// The entry:
//
//     membership_array[k]
//
// indicates whether the element:
//
//     k + 1
//
// belongs to the subset.
//
//
//
// Our recursive function has three parameters:
//
//     membership_array
//
//         Records the decisions already made.
//
//     capacity
//
//         The number of elements in the original
//         set.
//
//     current_index
//
//         The index of the element whose membership
//         we must decide next.
//
//
//
// The trivial case occurs when:
//
//     current_index == capacity.
//
// At that point, we have decided whether every
// element belongs to the subset.
//
// We can therefore print the completed subset.
//
//
//
// Otherwise, we make two recursive calls:
//
//     1. Include the current element.
//
//     2. Exclude the current element.
//
// Each recursive call advances current_index,
// so eventually we reach the trivial case.


// Function declarations
int main();

void print_subsets(
    unsigned int const n
);

void print_subsets(
    bool        membership_array[],
    std::size_t const capacity,
    std::size_t const current_index
);


// Function definitions
int main() {
    for ( unsigned int n{ 0 }; n <= 6; ++n ) {
        std::cout << "-------- " << n << " --------"
                  << std::endl;

        print_subsets( n );
    }

    return 0;
}


// This non-recursive function is the interface
// used by the caller.
//
// It creates and initializes the membership array,
// calls the recursive function, and then releases
// the dynamically allocated memory.
//
//
//
// IMPORTANT:
//
// An array declared as:
//
//     bool membership_array[n];
//
// where n is not a compile-time constant is a
// variable-length array.
//
// Variable-length arrays are NOT part of standard
// C++11, C++14, or later versions of standard C++.
//
// Some compilers accept them as an extension,
// but portable C++ code cannot rely on them.
//
//
//
// Here, we dynamically allocate the array.
//
// We use value initialization:
//
//     new bool[n]{}
//
// so every entry is initially false.
//
// We then release the memory with:
//
//     delete[].
//
// In a later course, we would normally use a
// standard container or an appropriate resource-
// managing object instead of managing dynamic
// memory ourselves.

void print_subsets(
    unsigned int const n
) {
    bool *membership_array{ new bool[n]{} };

    print_subsets(
        membership_array,
        n,
        0
    );

    delete[] membership_array;
}


// The recursive function.
//
// PRECONDITIONS:
//
//     current_index <= capacity
//
// and:
//
//     If capacity > 0, membership_array must
//     point to an array containing at least
//     capacity Boolean entries.
//
//
//
// POSTCONDITION:
//
//     Print every subset consistent with the
//     membership decisions already made for
//     indices:
//
//         0, 1, ..., current_index - 1.
//
//     The remaining membership decisions are
//     explored recursively.

void print_subsets(
    bool        membership_array[],
    std::size_t const capacity,
    std::size_t const current_index
) {
    assert( current_index <= capacity );
    assert( (capacity == 0) || (membership_array != nullptr) );

    if ( current_index == capacity ) {
        // TRIVIAL CASE
        //
        // Every membership decision has been made.
        //
        // Print the corresponding subset in the form:
        //
        //     {1, 3, 5}
        //
        // We use a Boolean variable named first
        // to avoid printing an unnecessary comma
        // before the first element.
        //
        // If no elements belong to the subset,
        // we print:
        //
        //     {}

        std::cout << "{";

        bool first{ true };

        for ( std::size_t k{ 0 }; k < capacity; ++k ) {
            if ( membership_array[k] ) {
                if ( !first ) {
                    std::cout << ", ";
                }

                std::cout << (k + 1);

                first = false;
            }
        }

        std::cout << "}" << std::endl;
    } else {
        // NON-TRIVIAL CASE
        //
        // We have not yet decided whether the
        // element:
        //
        //     current_index + 1
        //
        // belongs to the subset.
        //
        // We must explore BOTH possibilities.

        // First possibility:
        //
        // Include the current element.

        membership_array[current_index] = true;

        print_subsets(
            membership_array,
            capacity,
            current_index + 1
        );


        // Second possibility:
        //
        // Exclude the current element.

        membership_array[current_index] = false;

        print_subsets(
            membership_array,
            capacity,
            current_index + 1
        );
    }
}














































// Tracing the recursion
//
// Consider:
//
//     print_subsets( 3 );
//
// We are generating the subsets of:
//
//     {1, 2, 3}.
//
// At every level of recursion, we decide whether
// one additional element belongs to the subset.
//
// We first include the element, then exclude it.
//
//
//
// The recursion tree is:
//
//                            {}
//                             |
//                    Decide about 1
//                       /          \
//                  Include        Exclude
//                    /                \
//                  {1}                {}
//                   |                  |
//             Decide about 2    Decide about 2
//               /       \          /       \
//             {1,2}    {1}       {2}        {}
//               |       |         |          |
//             Decide about element 3 in each case
//              / \     / \       / \        / \
//             /   \   /   \     /   \      /   \
//
//            {1,2,3}  {1,2}   {1,3}  {1}
//
//                     {2,3}   {2}     {3}   {}
//
//
// The final line contains all eight subsets.
//
//
//
// The exact order produced by our program is:
//
//     {1, 2, 3}
//     {1, 2}
//     {1, 3}
//     {1}
//     {2, 3}
//     {2}
//     {3}
//     {}
//
// Why this order?
//
// Because the function explores the branch that
// INCLUDES the current element before the branch
// that EXCLUDES it.
//
//
//
// An experiment
//
// Exchange the two recursive branches:
//
//     First exclude the current element.
//
//     Then include the current element.
//
// Does the program still generate every subset?
//
// Does it generate them in the same order?
//
//
//
// A second experiment
//
// Instead of printing:
//
//     current_index + 1
//
// print:
//
//     current_index.
//
// What set are we now finding the subsets of?
//
//
//
// A third experiment
//
// Modify the program so that it prints only
// subsets containing exactly three elements.
//
// Think about whether you should:
//
//     Generate every subset and count its elements
//     before printing.
//
// or:
//
//     Keep track of the number of included
//     elements during recursion.
//
// Could you stop exploring a branch as soon as
// you have included too many elements?














































// Understanding the recursive structure
//
// The key observation is that every element
// introduces two choices.
//
// For example, consider the set:
//
//     {1, 2, 3}.
//
// The first decision is:
//
//     Include 1.
//
// or:
//
//     Exclude 1.
//
// In either case, we still have exactly the same
// kind of problem:
//
//     Decide which of the remaining elements
//     belong to the subset.
//
// This is what makes recursion appropriate.
//
//
//
// What information must we preserve?
//
// The Boolean membership array records the
// decisions already made.
//
// The current_index tells us which decision
// remains to be made next.
//
// The capacity tells us when there are no more
// decisions to make.
//
//
//
// Why do we not need to undo every decision?
//
// Notice that after exploring:
//
//     membership_array[current_index] = true;
//
// we explicitly assign:
//
//     membership_array[current_index] = false;
//
// before exploring the second branch.
//
// At each level, we overwrite the membership
// decision for the current element.
//
// When a recursive call returns, the entries
// corresponding to earlier elements have not
// been changed by that call.
//
// The entries corresponding to later elements
// may have been changed, but they will be
// overwritten before they are used again.
//
// Therefore, we do not need to restore the
// entire membership array after every call.
//
//
//
// Why does the recursion terminate?
//
// Every non-trivial call makes recursive calls
// with:
//
//     current_index + 1.
//
// The capacity remains unchanged.
//
// Thus, current_index eventually reaches:
//
//     capacity.
//
// At that point, the function prints a subset
// and makes no further recursive calls.
//
//
//
// How many subsets are printed?
//
// Let S(n) be the number of subsets generated
// from n elements.
//
// For an empty set:
//
//     S(0) = 1.
//
// For n > 0, every subset either contains the
// first element or does not contain it.
//
// In each case, we must generate all subsets
// of the remaining n - 1 elements.
//
// Thus:
//
//     S(n) = 2*S(n - 1).
//
// Repeated substitution gives:
//
//     S(n) = 2^n.
//
// Therefore:
//
//     S(0) = 1
//     S(1) = 2
//     S(2) = 4
//     S(3) = 8
//     S(4) = 16
//     S(5) = 32
//     S(6) = 64.
//
//
//
// Runtime
//
// There are:
//
//     2^n
//
// completed subsets.
//
// Each completed subset requires scanning the
// membership array, which contains n entries.
//
// Consequently, the total time required to
// generate AND PRINT the subsets is:
//
//     Theta(n*2^n)
//
// for n >= 1.
//
// The recursive branching itself requires:
//
//     Theta(2^n)
//
// calls, but printing each completed subset
// requires an additional Theta(n) scan.
//
//
//
// Space
//
// The membership array contains n entries.
//
// The maximum recursion depth is n + 1 calls.
//
// Therefore, the auxiliary space requirement
// is:
//
//     Theta(n).
//
// This excludes any storage used internally
// by the output stream.
//
//
//
// Why is this algorithm exponential?
//
// Every time we add one element to the original
// set, the number of subsets doubles.
//
// For example:
//
//     n = 10       1,024 subsets
//
//     n = 20   1,048,576 subsets
//
//     n = 30   1,073,741,824 subsets.
//
// Even if the algorithm were extremely efficient,
// merely printing every subset would eventually
// become prohibitively expensive.
//
// This is an example of an OUTPUT-SENSITIVE
// problem.
//
// The output itself is exponentially large.
//
// No algorithm that explicitly prints every
// subset can avoid producing all 2^n subsets.
//
//
//
// Questions
//
// 1. What is the trivial case?
//
// 2. Why does every non-trivial call make
//    exactly two recursive calls?
//
// 3. What does membership_array[k] represent?
//
// 4. Why is current_index incremented in each
//    recursive call?
//
// 5. Why is the empty set printed?
//
// 6. How many subsets does a set containing
//    seven elements have?
//
// 7. What changes if we explore the exclusion
//    branch before the inclusion branch?
//
// 8. Why does this implementation use only
//    Theta(n) auxiliary space even though it
//    generates 2^n subsets?
//
// 9. Why is the total runtime Theta(n*2^n)
//    rather than merely Theta(2^n)?
//
// 10. Could an algorithm that explicitly prints
//     all subsets of a set containing n elements
//     have polynomial runtime in n?
//
// 11. How would you modify this algorithm to
//     print only subsets of a specified size?
//
// 12. How would you modify it to count the
//     subsets without printing them?
//
//
//
// The central idea
//
// At each step, make one decision:
//
//     Include the current element.
//
// or:
//
//     Exclude the current element.
//
// Then recursively solve the same problem for
// the remaining elements.
//
// This include/exclude pattern appears in many
// important algorithms, including:
//
//     Generating combinations.
//
//     Solving subset-sum problems.
//
//     Exploring possible selections of items.
//
//     Solving the 0-1 knapsack problem.
//
//     Backtracking algorithms.
//
// It is one of the fundamental patterns of
// recursive algorithm design.