K-subsets

Why it matters

Many problems ask you to pick a small group from a bigger list. Choose 3 candidates for an interview panel from 10 people. Pick 2 toppings for a pizza from a menu of 6. Pick 5 cards from a deck to form a hand. The answer is a list of groups, and each group must appear exactly once. If a program returns the same group twice, or returns a group that uses one item twice, the totals it reports are wrong.

The previous lesson, Subsets, decided for every item whether to include it. Here each group has a fixed size, so the search has a different stopping rule and a new rule for where the next pick can come from. This lesson shows both rules.

Terms used here

A combination is a group of items where the order does not matter. {1, 2} and {2, 1} are the same combination, so the search should produce only one of them.

The letter n is the number of items you can pick from. The letter k is how many items each group must contain. Choosing k from n means every answer has exactly k items.

A start index is a position in the list. The search only looks at items at that position or later. It is a number that the recursive function passes down to itself.

The idea: pick in list order

Suppose four people are waiting in a line: Ana, Ben, Chen and Dev. You need a pair for a team. Ana is at position 0, Ben at position 1, Chen at position 2 and Dev at position 3.

Use one simple rule. Make the picks in list order. Pick the first person from the line, then pick the second person only from people who stand after the first one. The pair Ana and Ben is allowed. The pair Ben and Ana is not, because Ana stands before Ben, and the search never looks back up the line. Each pair appears exactly once.

Count the pairs to check the rule. Four people and pairs give six groups: Ana with Ben, Ana with Chen, Ana with Dev, Ben with Chen, Ben with Dev, and Chen with Dev. Mathematicians write the number of ways to choose k from n as C(n, k), read as "n choose k". Its value is n! divided by (k! times (n minus k)!). For n = 4 and k = 2 that is 24 divided by (2 times 2), which is 6. The exclamation mark means factorial, the product of all whole numbers up to that value. So 4! is 4 times 3 times 2 times 1, which is 24.

The search can be drawn as a tree. Each level of the tree makes one more pick. Here is the tree for choosing 2 from the list {1, 2, 3}:

start
 +-- pick 1 (later choices: 2, 3)
 |    +-- {1, 2}
 |    +-- {1, 3}
 +-- pick 2 (later choices: 3)
 |    +-- {2, 3}
 +-- pick 3 (later choices: none)
      dead end, nothing is added

The branch for pick 3 leads nowhere. No item comes after 3 in the list, so this branch cannot make its second pick. The search finishes with three groups, and C(3, 2) is also 3. The code below walks this tree in the same order.

Stopping at k instead of at the end of the list

The subsets lesson stops when every item has been decided. A k-subset search stops at a different point: when the current group has k items. Here is the base case:

if the group has k items: save a copy and return

The rest of the search has the same shape as before. It has a loop over the choices, a step that adds one choice, a recursive call, and a step that removes the choice again. The new part is the loop's start, which is the start index. Each recursive call passes i + 1 so that the next pick must come later in the list.

The code, step by step

The first program chooses 2 items from {1, 2, 3, 4}, and then two bigger examples. The helper print_set only prints a group in braces.

Compile it with g++ -std=c++20 -Wall -Wextra and run it. The output is:

Example 1: choose 2 from {1, 2, 3, 4}
{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}
count = 6
 
Example 2: choose 3 from {1, 2, 3, 4, 5}
count = 10
first = {1, 2, 3}
last  = {3, 4, 5}
 
Example 3a: plain search on {2, 2, 3}, choose 2
{2, 2} {2, 3} {2, 3}
count = 3
Example 3b: sorted, skip repeated values at each level
{2, 2} {2, 3}
count = 2

Read choose line by line.

The if at the top checks whether the group is full. cur is the group being built, and out.push_back(cur) stores a copy of it. The copy matters. If the function stored a reference, every saved group would change as the search continued.

The for loop tries each position from start to the last item. The index i is the position of the item being tried now.

cur.push_back(a[i]) adds the item to the group. The recursive call passes i + 1 as the new start, so the next pick must come from a later position. That single number is what stops {2, 1} from appearing after {1, 2}.

cur.pop_back() removes the item again. This is the undo step from the subsets lesson. Without it, the group would keep the old picks, and every later branch would start from the wrong group.

Now compare the counts with the formula. Example 1 gives 6, which matches C(4, 2). Example 2 gives 10. The formula is 5! divided by (3! times 2!), which is 120 divided by (6 times 2), which is 10. The first group is {1, 2, 3} because the search always starts with the lowest positions. The last group is {3, 4, 5}, the last one that still leaves enough items after it.

A harder example: a group must reach a target sum

Choosing 3 numbers from 1 to 9 whose sum is 15 is a classic puzzle. The answer lists the rows, columns and diagonals of a 3 by 3 magic square, where every line adds up to 15. The search from this lesson solves it with one change: the base case checks the sum before it saves the group.

The output is:

triples from 1..9 with sum 15: 8 calls=130
1 5 9
1 6 8
2 4 9
2 5 8
2 6 7
3 4 8
3 5 7
4 5 6

The search still produces each triple once, because of the start index. The sum is added up only at the leaves, which are the full groups. Nothing about the tree has changed.

The count of calls explains how much work the search does. The list has C(9, 3), which is 84, possible triples. Each triple is one leaf of the tree. The other calls are the nodes that hold one or two items, and there are 1 + 9 + 36 = 46 of them. The total is 84 + 46 = 130. A later lesson, Pruning backtracking, cuts branches early when the sum can no longer reach the target. This version checks every triple, which is slower but easier to read.

When the input has repeated values

Example 3 shows what happens when the list contains the same value twice. The plain search gives {2, 3} twice. The two 2s are at different positions, so the search treats them as different items. The output looks like a duplicate because the values are equal.

The fix has two parts. First sort the list, so equal values sit next to each other. Second, at each loop level, skip a position whose value equals the value just before it. The skip only happens when i > start. At the first position of the loop, there is no earlier sibling at this level with the same value, so the item must be tried.

The skip rule removes the duplicate for this reason. Take the sorted list {2, 2, 3}. The branch that picks the first 2 already tries every group that starts with a 2 and continues with items from the second position on. That includes the group made from the second 2 and the 3. The branch that picks the second 2 would produce the same value group again, so the search skips it.

Common mistakes

The first common mistake is passing i instead of i + 1 to the recursive call. The search then allows the same item to be picked again. Here is a version with that one change. Run on {1, 2, 3} with k = 2, it prints:

wrong_start count = 6
1 1 | 1 2 | 1 3 | 2 2 | 2 3 | 3 3 |

The groups 1 1, 2 2 and 3 3 use one item twice. The count is 6 instead of 3, which is what a student usually notices first. The fix is to pass i + 1.

The second mistake is forgetting pop_back. Without the undo step, cur keeps every item it has ever received, and the search stops producing new groups. With the input {1, 2, 3} and k = 2 and the pop_back line removed, the program prints:

no_undo count = 1

Only one group is saved. The rest of the search runs, but cur already has the wrong contents when each later branch starts. The lesson is that every push_back in a backtracking function needs a matching pop_back on the same path.

The third mistake is comparing sizes with signed and unsigned numbers. The size() function returns an unsigned number, which cannot be negative, and k is an int. Comparing them with cur.size() == k triggers this warning when you compile with -Wall -Wextra:

warning: comparison of integer expressions of different signedness:
‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]

The code in this lesson uses (int)cur.size() to avoid the warning. A cast changes the type for one expression. The same warning appears on any size() comparison, including strings, so use the same cast in each place or use std::ssize, which returns a signed number.

The fourth mistake is using the skip rule on an unsorted list. The rule only looks at the item just before it, so equal values must be next to each other. Here is {2, 3, 2}, which has the same values as the sorted list {2, 2, 3}:

Ex5 unsorted {2,3,2} choose 2: {2, 3} {2, 2} {3, 2}
count = 3

The output contains {2, 3} and {3, 2}, which are the same two values in different orders. The sorted version gives only {2, 2} and {2, 3}. Sort first, then apply the skip rule.

Practice

Exercise 1

How many groups does the search produce when it chooses 3 items from {1, 2, 3, 4, 5, 6}? Use the formula first, then check your answer by changing the code in this lesson.

Show the answer

The formula gives C(6, 3), which is 6! divided by (3! times 3!). That is 720 divided by (6 times 6), which is 20. Running choose_unique on the sorted list {1, 2, 3, 4, 5, 6} with k = 3 prints count = 20.

Exercise 2

Change the search so it prints only the groups whose numbers add up to 6. Use choose on {1, 2, 3, 4, 5} with k = 2. Hint: add the numbers in cur only when the group is full.

Show the answer

Add a sum check in the base case. Replace the out.push_back(cur) branch with a loop that adds the items, then print the group when the total is 6:

int total = 0;
for (int x : cur) total += x;
if (total == 6) { print_set(cur); cout << " "; }

The output is {1, 5} {2, 4}. These are the only two pairs from {1, 2, 3, 4, 5} that add up to 6.

Exercise 3

The list {1, 1, 1, 2} has three equal 1s. Using choose_unique with k = 2, what groups are printed, and how many are there?

Show the answer

The output is {1, 1} {1, 2} with a count of 2. The sorted list is already in order. The first 1 is tried at the first level, and the two later 1s are skipped at that same level. The pair {1, 1} is produced once, and {1, 2} once.

Exercise 4

What does choose_unique print for k = 1 on {7, 8, 9}? What does it print for k = 0?

Show the answer

For k = 1 the output is {7} {8} {9}, which is one group per item. For k = 0 the base case is true at the very start, so the search saves one empty group. The count is 1 and the group is {}. Some problems need this edge case, so the code handles it without a special branch.

Exercise 5

Explain why the skip rule must look at a[i - 1] only after the list has been sorted.

Show the answer

The skip rule only detects equal values that sit next to each other in the list. If equal values are separated, the rule does not see them as equal. The unsorted list {2, 3, 2} gives three groups, including {2, 3} and {3, 2}, which contain the same two values. Sorting the list first puts the two 2s next to each other, and the output drops to two groups.

Summary

• A k-subset search makes exactly k picks, and its base case is a full group, not the end of the list.
• Pass i + 1 to the recursive call so that each pick comes from a later position. This prevents repeated groups and self-picks.
• Every push_back on the way down needs a pop_back on the way back up.
• To avoid duplicate values in the output, sort the input first, then skip a position whose value equals the one just before it, but only when i > start.
• The count of groups is C(n, k), and checking your output against that number catches most mistakes early.