Sidon Sets

#include <iostream>
#include <set>

//For timing
#include <chrono>
using namespace std::chrono;

using namespace std;

static int totalSets = 0;
static int maxSize = 0;
static set<int> largestset;

void printSet(set<int> myset) {
    cout << "Sidon size " << myset.size() << ": ";
    for (int elem : myset) {
        cout << elem << ", ";
    }

    cout << endl;
}

static int sizeMinToPrint = 1;
void countSet(set<int> myset) {
    totalSets++;

    if (myset.size() > maxSize) {
        maxSize = myset.size();
        largestset = myset;

    }

    return;
}


void sidon(int n, int max, set<int>& progress, set<int>& sums) {

    //base case
    if (n > max) return;

    bool validSet = true;

    //Now we must verify that n will not make a non-distinct sum
    //We check that every sum of n and an element in the set is new
    progress.insert(n);

    for (int elem : progress) {
        int newSum = elem + n;
        //A sum is already possible; not a sidon set
        if (sums.count(newSum)) {
            validSet = false;
            break;
        }
    }

    //If the set including n is a sidon set, we try to add it and recurse
    if (validSet) {
        for (int elem : progress) {
            int newSum = elem + n;
            sums.insert(elem+n);
        }
        //Print out progress as possible sidon set
        countSet(progress);

        sidon(n+1, max, progress, sums);

        //Remove all sums including n
        //This is done so we do not have to make copies of the set, increasing performance
        for (int elem : progress) {
            int newSum = elem + n;
            sums.erase(newSum);
        }
    }


    //Unchoose
    progress.erase(n);

    //Try to make sidon sets not including n
    sidon(n+1, max, progress, sums);

}

void sidon(int max) {
    totalSets = 0;
    maxSize = 0;

    set<int> progress;
    set<int> sums;
    sidon(1, max, progress, sums);
    cout << "Found " << totalSets << " Sidon sets from 1 to " << max << "." << endl;
    cout << "The max set size is " << maxSize << "." << endl;
    cout << "One such largest set is ";
    printSet(largestset);
}




int main()
{
    for(int i = 0; i < 10; i++) {
        cout << "." << endl;
    }

    // Get starting timepoint
    auto start = steady_clock::now();

    sidon(26);

    // Get ending timepoint
    auto stop = steady_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);

    cout << "Time taken by function: "
         << duration.count() << " millseconds" << endl;

    return 0;
}