Stairclimber

vector< vector<int> > get_ways(int num_stairs) {
    /* Returns a vector of vectors of ints representing
    the different combinations of ways to climb num_stairs
    stairs, moving up either 1, 2, or 3 stairs at a time.
    Optimized to use a modified integer partition algorithm. */
    vector<vector<int>> all_ways;
    vector<int> p(num_stairs, 0);
    if (num_stairs < 4) {
        all_ways.push_back(vector<int>{num_stairs});
    }
    int k = 0;
    p[k] = num_stairs;
    while (true) {
        // Generate next partition
        // Find the rightmost non - one value in p[].
        // Also, update the rem_val so that we know
        // how much value can be accommodated
        int rem_val = 0;
        while (k >= 0 && p[k] == 1) {
            rem_val += p[k];
            k -= 1;
        }
        // if k < 0, all the values are 1 so
        // there are no more partitions
        if (k < 0) return all_ways;
        // Decrease the p[k] found above and adjust the rem_val
        p[k] -= 1;
        rem_val += 1;
        // Ensure values are below or equal to 3 before increment
        while (p[k] > 3) {
            p[k] -= 1;
            rem_val += 1;
        }
        // Copy rem_val to next position
        // and increment position
        p[k + 1] = rem_val;
        k += 1;
        // Keep values only if they at most 3
        if (rem_val > 3) continue;
        vector<int> valid_p;
        // Add non-zero values (everything before k + 1)
        for (int i=0; i < k + 1; i++) {
            valid_p.push_back(p[i]);
        }
        all_ways.push_back(valid_p);
    }
}

void display_ways(const vector< vector<int> > &ways) {
    /* Iterates through the ways to climb the stairs and displays them
    **Must be printed in reverse for the partition algorithm */
    int width = ways.size() == 0 ? 1 : log10(abs(long(ways.size()))) + 1;
    // for (unsigned int i=0; i < ways.size(); i++) {
    for (unsigned int i=ways.size() - 1; i >= 0; i--) {
        cout << setw(width) << ways.size() - i << ". [";
        for (unsigned int j=0; j < ways[i].size(); j++) {
            cout << ways[i][j];
            if (j < ways[i].size() - 1) {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }
}