Todos os subconjuntos de um conjunto

Faz um programa que imprima no ecrã todos os subconjuntos de um conjunto. O input do programa deve ser um número n que indica o número de elementos do conjunto. Para simplificar, assume que os elementos do conjunto são os números: {1, 2, ..., n}.

DICA: O número de subconjuntos de um conjunto com n elementos é 2 elevado a n. Por exemplo, o conjunto {1,2,3} tem 8 subconjuntos. (nota: a regra é válida para o conjunto vazio (n=0)).

Exemplo do programa ao ser executado:

     Introduz um número: 3
     Os subconjuntos de {1,2,3} são:

        {}
        {1}
        {2}
        {3}
        {1,2}
        {1,3}
        {2,3}
        {1,2,3}

Nota: O output do programa não tem que vir necessáriamente nesta ordem. O importante é que todos os subconjuntos apareçam.