All possible combinations of elements

combinations

I'd like to know a possible algorithm to calculate all possible combinations, without repetitions, starting from length=1 until length=N of N elements.

Example:

Elements: 1, 2, 3.

Output:

1
2
3
12
13
23
123

Best Solution

Look at the binary presentation of the numbers 0 to 2^n - 1.

n = 3

i  Binary  Combination

   CBA

0  000
1  001     A
2  010       B
3  011     A B
4  100         C
5  101     A   C
6  110       B C
7  111     A B C

So you just have to enumerate the numbers 1 to 2^n - 1 and look at the binary representation to know which elements to include. If you want to have them ordered by the number of elements post sort them or generate the numbers in order (there are several example on SO).