Dynamic programming - Generate power set given a set

1. Problem description
Power set is the the collection of all possible non-empty subsets given a set that is consisted of a list of  numbers. For example
SET = {1, 4, 6}
PowerSet = {{1}, {1, 4}, {4}, {1, 6}, {1, 4, 6}, {4, 6}, {6}}

2. Problem analysis based on dynamic programming
The key of dynamic program is to find out the sub-problem and then work out the relationship between the problem and its sub-problem. It can be described as the g(f(n), f(n-1)).

Give a set of n different numbers,
     SET = {Mn, Mn-1, ..., M2, M1}
f(n) is the power set of
    {Mn, Mn-1, ..., M2, M1}
f(n-1) is the power set of
    {Mn-1, Mn-2, ..., M2, M1}

Let's assume that the f(n-1) is
    {C1, ..., Cx}, the power set has size of "x".
f(n) will be the all the combination of Mn with f(n-1).
Then f(n) will be
    {C1, ..., Cx, {C1, Mn}, {C2, Mn}, ..., {Cx, Mn}, {Mn}}

The formulation:
The g(f(n), f(n-1)) can be formulated as
    f(n) will be all the combination of f(n-1) with Mn plus one extra subset {Mn}
    sizeOf(f(n)) = 2*sizeOf(f(n-1)) + 1
    f(1) is {M1} and sizeOf(f(1)) = 1

3. Solution implementation
Two implementations are provided. One is recursive function and another is non-recursive.

*********************************************************************************
#include <vector>

typedef std::vector<int> SET;
typedef std::vector<SET> POWERSET;

void RelationshipOfProblemAndSubproblem(POWERSET& result, int Mn)
{
    size_t len = result.size();

    // copy f(n-1) and append Mn to each element of f(n-1)
    // to generate {{C0, Mn}, {C1, Mn}, ..., {Cx, Mn}}
    // All together in "result" will be f(n)
    // { C0, C1, ..., Cx, {C0, Mn}, {C1, Mn}, ..., {Cx, Mn}, {Mn}}
    for (size_t i = 0; i < len; ++i) {
        result.push_back(result[i]);
    }
    for (size_t i = len; i < result.size(); ++i) {
        SET& curSet = result[i];
        curSet.push_back(Mn);
    }

    // Append {Mn} to the result
    result.push_back(SET(1, Mn));
}


// Recursive implementation
void PowerSetR(const SET& s, size_t pos, POWERSET& result)
{
    if (pos == s.size()) {
        return;
    }

    PowerSetR(s, pos + 1, result);
    RelationshipOfProblemAndSubproblem(result, s[pos]);
}

// Non-recursive implementation
POWERSET PowerSetNR(const SET& s)
{
    POWERSET result;
 
    for (size_t i = 0; i < s.size(); ++i) {
        RelationshipOfProblemAndSubproblem(result, s[i]);
    }

    return result;
}

int _tmain(int argc, _TCHAR* argv[])
{
    SET s;
    s.push_back(1);
    s.push_back(4);
    s.push_back(6);

    POWERSET resultR;
    PowerSetR(s, 0, resultR);

    POWERSET resultNR = PowerSetNR(s);

return 0;
}
*********************************************************************************

In this case the non-recursive implementation is even neater than the recursive version. But in my opinion the recursive implementation is much easier to understand the idea. In the recursive implementation the last element of SET is M0, however in the non-recursive the first element of SET is M0. Therefore the result generated by the two implementations will be in the reverse order. The elements in "resultR" is in the reverse order of "resultNR".