Generate Combinations in Java
Problem
Generating combinations means listing out every possible group of a fixed size from a larger set, where the order within each group doesn't matter — unlike calculating just the count of how many such groups exist, this actually produces each one.
Given a set of items and a size k, print every combination of k items chosen from that set.
Java Program
public class GenerateCombinationsRecursion {
static char[] items = {'A', 'B', 'C'};
static int k = 2;
static void generate(int start, StringBuilder current) {
if (current.length() == k) {
System.out.println(current);
return;
}
for (int i = start; i < items.length; i++) {
current.append(items[i]);
generate(i + 1, current);
current.deleteCharAt(current.length() - 1); // backtrack before trying the next item
}
}
public static void main(String[] args) {
generate(0, new StringBuilder());
}
}Output
Core Logic
Trying each remaining item in turn, adding it to the partial combination, recursing to fill the rest, and then removing it again before trying the next one, explores every valid group of the right size exactly once.
- 1
generate(start, current)tracks which items are still eligible to be added and what's been chosen so far. - 2The base case
if (current.length() == k)fires once the partial combination has reached the target size, printing it. - 3The loop tries every item from
startonward, appending one, recursing withi + 1so the same item can't be picked twice, then removing it again — the classic backtracking pattern. - 4Starting the loop from
startrather than0every time is what stopsBAfrom being generated alongsideAB— once an item is skipped, it's never revisited.
{A, B, C}: picking A then trying B and C gives AB and AC; backtracking to just B then trying C gives BC — three combinations in total.Key Point: Removing the just-added item after recursing — the backtracking step — is what lets the same current buffer be reused for every branch instead of building a fresh copy at each call.
Why: The recursion produces exactly C(n, k) complete combinations, and the partial combination being built never holds more than k characters, matching the recursion's depth.