Program Generarea_submultimilor_backtracking;
  uses crt;
  type stiva=array[1..100]of byte;
  var st:stiva;
      as,ev:boolean;  {as=are_succesor; ev=este_validat}
      i,j,k,n:integer;

procedure tipareste_solutia;
 var it:integer;
begin
 write('{');
 for it:=1 to k-1 do write(st[it],',');
 write(st[k],'}');
 writeln;
end;

begin
  clrscr;
    write('n='); readln(n);
      k:=1; st[k]:=0;
      while (k>0) do
        begin
          Repeat
            if st[k]<n then
                begin
                  st[k]:=st[k]+1;
                  as:=true;
                end
                  else as:=false;
             if as then
               begin
                 ev:=true;
                 for i:=1 to k-1 do if st[i]>=st[k] then ev:=false;
               end;
           until not as or (as and ev);
             if as then
                     begin
                     tipareste_solutia;
                     k:=k+1;
                     st[k]:=0;
                     end
                   else
                     k:=k-1;
              end;
readln;
end.