How to Generate Combinations

As programmers, occasionally
we come across cases where we
have to generate all possible
combinations of a set.
Now, I know the natural
solution is recursive but
I sometimes used to struggle
with getting it right.
(Need to generate

**permutations**? That's the next post) If you are in the same situation, I'd like to share how I finally discovered my favorite method for generating combinations in this post.
There are two possible
solutions for generating
combinations –
(1) recursive
and
(2) iterative.
My favorite method is the
iterative because it uses a
really neat trick, but I’ll
start with explaining the
elegant recursive solution.

import java.util.ArrayList;
import java.util.List;
class GeneratingCombinations {

The Recursive Method

In this method, we go through
each element and either
(a) Add it to the
combination or
(b) Not add it to the
combination
Then, whenever we reach the
last element we have
generated a new combination!

Simple? Let's try it below.

private void recursive_combinations(List<Object> combination,
int ndx, Object[] elems) {
if(ndx == elems.length) {
// (reached end of list after selecting/not selecting)
System.out.println(combination);
} else {
// (include element at ndx)
combination.add(elems[ndx]);
recursive_combinations(combination, ndx+1, elems);
// (don't include element at ndx)
combination.remove(elems[ndx]);
recursive_combinations(combination, ndx+1, elems);
}
}
public void recursive_combinations_start(Object[] elems) {
List<Object> combination = new ArrayList<>();
recursive_combinations(combination, 0, elems);
}

The Iterative Method

Now for my favorite method. I
love this because it uses a
little trick – think about
the elements “standing” one
next to the other. Under it
we imagine a little switch –
“on” if the element is in the
set, “off” if it isn’t:

On…off…on…off… sounds
familiar? It “looks like” the
binary representation of a
number. And what I find so
delightful is that – yes – we

*can*use the binary representation of a number to generate all possible combinations! The numbers from 0 to (2^n-1) contain, in their bits, all the combinations we need! This is simple and fun to code:
public void iterate_combinations(Object[] elems) {
int n = elems.length;
for(int num = 0;num < (1 << n);num++) {
List<Object> combination = new ArrayList<>();
for(int ndx = 0;ndx < n;ndx++) {
// (is the bit "on" in this number?)
if((num & (1 << ndx)) != 0) {
// then it's included in the list
combination.add(elems[ndx]);
}
}
// (show the current combination)
System.out.println(combination);
}
}

Which method is your
favorite? Do you know any
other methods? Let me know in
the comments below.

public static void main(String[] args) {
String elems[] = { "1", "2", "3", "4", "5" };
System.out.println("Recursive combinations");
new GeneratingCombinations().recursive_combinations_start(elems);
System.out.println("Iterate combinations");
new GeneratingCombinations().iterate_combinations(elems);
}
}

. . . . . . . . . .

. . . . . . . . . .

John says:

Thanks. This was a nice post.

theproductiveprogrammer says:

Glad you liked it!

saurabhhv says:

i like your style of explaining and pictures are like cherry on cake. The first article that i read from you was about understanding Big-O-Notation and that inspired me to checkout your blog.
Keep up the good work !
-Saurabh

. . . . . . . . . .