Definition
Combinations enumerates every size-K subset of the numbers 1 through N.
- Start value ensures numbers are picked in strictly increasing order, so each combination appears once.
- Base case is when the current combination holds exactly K numbers, and a copy is recorded.
- Pruning stops branches where the remaining numbers are fewer than the slots still needed.
- Result count is N choose K, the binomial coefficient C(N, K).
- Fixed-size specialization makes this a restricted version of general subset generation.
At National Bank of India, a review committee must pick exactly 3 auditors from a pool of 6, and HR wants every possible committee. Order does not matter, so picking auditors 1 and 2 is the same committee as 2 and 1. They build committees by always choosing auditors in increasing number, so each committee is formed exactly once, and they stop early if too few auditors remain to fill the committee.
Understanding the Concepts
What is the Combinations Problem?
Given two integers N and K, return all possible combinations of K numbers chosen from the range 1 to N. Order does not matter, so [1, 2] and [2, 1] are the same combination. The total number of results is the binomial coefficient C(N, K).
At National Bank of India, HR needs to enumerate every possible audit committee of exactly 3 members from a pool of 6 auditors.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class CombinationGenerator {
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(n, k, 1, new ArrayList<>(), result);
return result;
}
private static void backtrack(int n, int k, int start,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
// Prune: need (k - current.size()) more, only (n - i + 1) available
for (int i = start; i <= n - (k - current.size()) + 1; i++) {
current.add(i);
backtrack(n, k, i + 1, current, result);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
List<List<Integer>> committees = combine(6, 3);
System.out.println("Total committees: " + committees.size());
for (List<Integer> c : committees) {
System.out.println(c);
}
}
}
Total committees: 20
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
[2, 5, 6]
[3, 4, 5]
[3, 4, 6]
[3, 5, 6]
[4, 5, 6]
Why Does This Problem Matter?
Combinations is the fixed-size specialization of subset generation. While subsets generates all 2^n subsets of any size, combinations restricts to exactly K items. Many real-world problems ask for selections of a specific size: teams, committees, test suites, and portfolio allocations.
package com.bank.service;
public class CombinationCount {
// C(N, K) = N! / (K! * (N-K)!)
public static long binomial(int n, int k) {
if (k > n - k) k = n - k; // optimization: C(n,k) = C(n,n-k)
long result = 1;
for (int i = 0; i < k; i++) {
result = result * (n - i) / (i + 1);
}
return result;
}
public static void main(String[] args) {
System.out.println("C(6,3) = " + binomial(6, 3)); // 20
System.out.println("C(10,4) = " + binomial(10, 4)); // 210
}
}
C(6,3) = 20
C(10,4) = 210
How Does the Pruning Optimization Work?
The pruning bound limits the loop so we never start a number too large to leave enough remaining numbers to fill the combination. If we need k - current.size() more slots and only n - i + 1 numbers are available from i to N, we require n - i + 1 >= k - current.size(), which gives us i <= n - (k - current.size()) + 1.
This avoids exploring branches that can never produce a complete combination.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class PruningDemo {
static int withPruning = 0;
static int withoutPruning = 0;
public static void backtrackWithPruning(int n, int k, int start, List<Integer> current) {
if (current.size() == k) { withPruning++; return; }
for (int i = start; i <= n - (k - current.size()) + 1; i++) {
current.add(i);
backtrackWithPruning(n, k, i + 1, current);
current.remove(current.size() - 1);
}
}
public static void backtrackWithout(int n, int k, int start, List<Integer> current) {
if (current.size() == k) { withoutPruning++; return; }
for (int i = start; i <= n; i++) {
current.add(i);
backtrackWithout(n, k, i + 1, current);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
backtrackWithPruning(10, 3, 1, new ArrayList<>());
backtrackWithout(10, 3, 1, new ArrayList<>());
System.out.println("With pruning: " + withPruning + " complete combos found");
System.out.println("Without pruning: " + withoutPruning + " complete combos found");
}
}
With pruning: 120 complete combos found
Without pruning: 120 complete combos found
Both produce the same result, but pruning avoids exploring dead-end branches, reducing the total number of recursive calls.
How Is This Different from Permutations?
| Aspect | Combinations | Permutations |
|---|---|---|
| Order matters | No, {1,2} = {2,1} | Yes, [1,2] differs from [2,1] |
| Output count | C(N, K) | N! |
| Selection | Choose K from N | Arrange all N |
| Tracking | Start index (increasing picks) | Used array (any unused element) |
| Growth | Polynomial for fixed K | Factorial |
// Combinations of 5 choose 2 = 10
// Permutations of 5 = 120
What Are the Edge Cases?
The edge cases are K = 0 (one empty combination), K = N (one combination containing all numbers), and K > N (no valid combinations).
package com.bank.core;
public class CombEdgeCases {
public static void main(String[] args) {
// K = 0: one empty combination
System.out.println(CombinationGenerator.combine(5, 0)); // [[]]
// K = N: one full combination
System.out.println(CombinationGenerator.combine(3, 3)); // [[1, 2, 3]]
// K > N: no valid combinations
System.out.println(CombinationGenerator.combine(3, 5)); // []
}
}
[[]]
[[1, 2, 3]]
[]
What About Memory and Performance?
The total number of combinations is C(N, K). For moderate N and K the count is manageable, but for large N the output can be enormous. For example, C(30, 15) is over 155 million.
package com.bank.core;
public class CombFeasibility {
public static void main(String[] args) {
int[] ns = {10, 15, 20, 25, 30};
for (int n : ns) {
int k = n / 2;
System.out.println("C(" + n + "," + k + ") = " + CombinationCount.binomial(n, k));
}
}
}
C(10,5) = 252
C(15,7) = 6435
C(20,10) = 184756
C(25,12) = 5200300
C(30,15) = 155117520
What Are Common Mistakes?
The first mistake is forgetting to pass i + 1 instead of i as the next start, which would allow the same number to be picked twice. The second mistake is not pruning, which causes unnecessary recursion into branches that cannot complete.
// WRONG: allows same number twice
backtrack(n, k, i, current, result); // should be i + 1
// CORRECT: strictly increasing picks
backtrack(n, k, i + 1, current, result);
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Combination Sum: choose numbers that sum to a target instead of a fixed count.
- Combination Sum III: choose exactly K numbers from 1-9 that sum to a target (combines both constraints).
- Generate the k-th combination directly using the combinatorial number system.
- Count combinations without generating them using the binomial coefficient formula.
package com.bank.core;
public class CombFollowUp {
// C(N,K) can be computed iteratively without generating
// For the k-th combination, use the combinatorial number system
}
Visual Overview
Backtracking Tree for N=5, K=3: Start from 1: ┌──────────────────────────────────┐ │ Pick 1: │ │ Pick 2: [1,2,3] [1,2,4] [1,2,5] │ │ Pick 3: [1,3,4] [1,3,5] │ │ Pick 4: [1,4,5] │ │ Pick 5: PRUNED (need 2 more) │ ├──────────────────────────────────┤ │ Pick 2: │ │ Pick 3: [2,3,4] [2,3,5] │ │ Pick 4: [2,4,5] │ ├──────────────────────────────────┤ │ Pick 3: │ │ Pick 4: [3,4,5] │ ├──────────────────────────────────┤ │ Pick 4: PRUNED (need 3 slots) │ │ Pick 5: PRUNED │ └──────────────────────────────────┘ Total: C(5,3) = 10 combinations
Key Takeaway
Combinations enumerates every way to choose K numbers from the range 1 to N, where order does not matter. I solve it with backtracking using a start value and a current partial combination. When the combination reaches size K I record a copy. Otherwise I loop over numbers from the start onward, add one, recurse with the start advanced by one so picks strictly increase, and backtrack.
Choosing in strictly increasing order is exactly what distinguishes a combination from a permutation, because it fixes one canonical ordering per subset so no subset is produced twice. The optimization I always add is pruning: if the numbers still available are fewer than the slots I still need to fill, the branch cannot succeed, so I bound the loop end and avoid wasted work.
At National Bank of India I used this to enumerate audit committees, choosing exactly K auditors from a numbered pool of N so HR could run a conflict-of-interest review over every possible committee. I chose auditors in increasing order and pruned branches that could not be completed.
The result count is the binomial coefficient C(N, K), which can be computed directly without generating all combinations. For moderate N and K the enumeration is feasible, but for large N the output grows quickly, so I always check the count before generating.
Remember one sentence: pick numbers in increasing order up to size K, prune when not enough numbers remain, and the result count is C(N, K).
---