C++ sequences of numbers 1 and 2

[salem c]

Is that "don't know how to do it on paper" or "I can do it on paper, just not in code".

[lastchance]

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

int main()
{
   int n;
   cout << "Enter n: ";   cin >> n;
   vector< set<string> > S( 1 + n );
   S[1] = { "1" };
   if ( n > 1 ) S[2] = { "11", "2" };

   for ( int i = 3; i <= n; i++ )
   {
      for ( string s : S[i-2] ) S[i].insert( s + "2" );
      for ( string s : S[i-1] ) S[i].insert( s + "1" );
   }

   for ( string s : S[n] ) cout << s << " ";
}

Enter n: 6
111111 11112 11121 11211 1122 12111 1212 1221 21111 2112 2121 2211 222

This one usually uses less memory:

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main()
{
   set<string> SM2{ "1" }, SM1{ "11", "2" }, S;
   int n;
   cout << "Enter n: ";   cin >> n;

   if ( n == 1 )
   {
      S = SM2;
   }
   else if ( n == 2 )
   {
      S = SM1;
   }
   else
   {
      for ( int i = 3; i <= n; i++ )
      {
         S.clear();
         for ( string s : SM2 ) S.insert( s + "2" );
         for ( string s : SM1 ) S.insert( s + "1" );
         SM2 = SM1;
         SM1 = S;
      }
   }

   for ( string s : S ) cout << s << " ";
}

[JLBorges]

#include <iostream>
#include <algorithm>
#include <string>

// print all permutations of the (sorted) string
void print_perms( std::string str )
{
   do std::cout << str << ' ' ;
   while( std::next_permutation( std::begin(str), std::end(str) ) ) ;
   std::cout << '\n' ;
}

// make a string consisting of n1 '1's followed by n2 '2's
std::string make_string( std::size_t n1, std::size_t n2 )
{ return std::string( n1, '1' ) + std::string( n2, '2' ) ; }

void print_sequences_with_sum( std::size_t sum )
{
    std::cout << "sum == " << sum << '\n' ;

    // invariant: sum == num2s*2 + num1s ie . num1s = sum - num2s*2
    for( std::size_t num2s = 0 ; num2s <= sum/2 ; ++num2s )
        print_perms( make_string( sum - num2s*2, num2s ) ) ;

    std::cout << "\n--------------------\n" ;
}

int main()
{
    for( std::size_t s : { 7, 8 } ) print_sequences_with_sum(s) ;
}

http://coliru.stacked-crooked.com/a/7e6a0d80cd225217