Friends Pairing Problem in C++

For a group of n labelled friends, the task is to count the arrangements where each friend stays single or belongs to one pair. The friends pairing problem counts those arrangements.

I’ll explain the recurrence by splitting the cases for one fixed friend, then show how to calculate it in C++ using the two previous counts.

TL;DR

The friends pairing count follows f(n) = f(n − 1) + (n − 1)f(n − 2), because one chosen friend is either single or paired with one of the rest.

• Set f(0) = 1 and f(1) = 1.
• Use two previous values for O(n) time and O(1) extra space.
• Use a sufficiently wide type and check overflow when exact counts are required.

What Is the Friends Pairing Problem?

The friends pairing problem counts the distinct ways a group of n labelled friends can each remain single or join exactly one pair. A pair has no direction, so grouping friends 1 and 2 is the same arrangement as grouping 2 and 1.

For three friends, the four arrangements are all single, or one of the three possible pairs with the remaining friend single. For four friends, there are ten arrangements. These small results are useful checks for a program before trying a larger input.

I use f(0) = 1 because there is one way to arrange no remaining friends: add no pair. This convention makes the recurrence consistent at its lower boundary. Some problem statements begin at n = 1, but the implementation can still define zero safely.

Labelled friends are distinct people, so swapping which person occupies a particular position changes the arrangement when it changes who is paired with whom. The pairing itself has no order. That is why a pair such as A with B is one choice, rather than separate choices for A with B and B with A.

The word arrangement can make the problem sound like every friend must be matched. Each friend has two allowed states: single or part of one pair. A friend cannot appear in two pairs, and a group of three is outside the rules.

How to Solve the Friends Pairing Problem in C++ Step by Step

Build the answer from smaller group sizes, then keep only the two counts needed for the next calculation. This bottom-up choice avoids recursive call overhead and a table that the recurrence does not need.

Step 1: Choose one friend and split the cases

Fix one friend so each valid arrangement is counted once by what happens to that friend. If they stay single, arrange the other n − 1 friends in f(n − 1) ways.

If they pair up, they can choose any one of the remaining n − 1 friends. After choosing that partner, arrange n − 2 friends in f(n − 2) ways. The cases do not overlap, so add their counts:

f(n) = f(n - 1) + (n - 1) * f(n - 2)
f(0) = 1
f(1) = 1

The multiplier is n − 1 because the chosen friend is already fixed, leaving n − 1 possible partners. This case split is the reason the recurrence counts each arrangement once.

For four friends, the single case leaves three friends with four arrangements. The paired case has three partner choices, each leaving two friends with two arrangements. The total is 4 + 3 × 2 = 10.

Fixing one friend also avoids counting the same arrangement in different orders. Without that fixed choice, an arrangement containing two pairs could be generated by selecting either pair first. The recurrence instead assigns every arrangement to exactly one case based on the fixed friend.

Step 2: Keep the previous two counts

Each new count depends only on the counts for one and two fewer friends. The recurrence needs only two saved counts. After computing the next value, shift them forward.

The program below checks whether the multiplication and addition would exceed the maximum signed long long value before performing them. That makes the function return exact values when they fit and report overflow instead of silently relying on a wrapped result. Input is read as an integer, and a negative friend count is rejected.

The guard rearranges the fit condition rather than attempting the multiplication first. For positive i − 1, the next result fits when previousTwo × (i − 1) is no greater than max − previousOne. Dividing that remaining capacity by i − 1 gives the comparison in the code.

The loop starts at two because the two base cases are already available. For i equal to two, the expression gives f(1) + 1 × f(0), or 2. Each following iteration uses the newly shifted pair, so the loop invariant remains true until it reaches n.

Step 3: Compile the complete C++ program

Save this as friends_pairing.cpp. I compiled and ran this exact source with g++ 13.3.0 in C++17 mode. The terminal output below is from that execution.

#include <iostream>
#include <limits>
#include <stdexcept>

long long countWays(int n) {
    if (n < 0) throw std::invalid_argument("n must be non-negative");
    if (n == 0 || n == 1) return 1;

    long long previousTwo = 1;
    long long previousOne = 1;
    for (int i = 2; i <= n; ++i) {
        if (previousTwo > (std::numeric_limits<long long>::max() - previousOne) / (i - 1))
            throw std::overflow_error("result does not fit in long long");
        long long current = previousOne + (i - 1) * previousTwo;
        previousTwo = previousOne;
        previousOne = current;
    }
    return previousOne;
}

int main() {
    for (int n = 0; n <= 7; ++n)
        std::cout << "n=" << n << " ways=" << countWays(n) << '\\n';
}

Run it with g++ -std=c++17 -Wall -Wextra -pedantic friends_pairing.cpp -o friends_pairing followed by ./friends_pairing. The loop prints the counts from zero through seven, which makes the base values and several recurrence steps visible without asking the reader to trust an untested snippet.

n=0 ways=1
n=1 ways=1
n=2 ways=2
n=3 ways=4
n=4 ways=10
n=5 ways=26
n=6 ways=76
n=7 ways=232

The sequence begins 1, 1, 2, 4, 10, 26, 76, 232. In particular, the three-friend and four-friend results match the hand-counted examples. The screenshot shows the same compile-and-run command and output.

Each value counts complete arrangements, not the number of pairs in an arrangement. For example, five friends can produce an arrangement with zero pairs, an arrangement with one pair, or an arrangement with two pairs. The recurrence includes all of those possibilities without needing a separate loop for each possible pair count.

The sequence is useful as a small regression check when you change the implementation. If the value for four friends becomes 8, for example, the paired case has probably missed one of the three choices for the first friend’s partner. Checking a few known small inputs can catch that counting error before you inspect a large result.

Step 4: Check the cost of the algorithm

The loop computes one state for each size from 2 through n, so its running time is O(n). It stores two prior counts and the current count, giving O(1) auxiliary space.

A full dynamic-programming vector would also take O(n) time, but it stores every intermediate value. I chose the rolling variables because this task asks only for f(n), not for a history table or a reconstruction of arrangements.

The variable names describe the state just before an iteration. At i = 2, previousTwo holds f(0) and previousOne holds f(1). The formula therefore calculates f(2), then the assignments move the window forward so the next iteration has f(1) and f(2).

This is still dynamic programming. Dynamic programming stores answers to smaller subproblems so they are not recomputed. A table is useful when later code needs many earlier answers, while two variables are enough when each state depends on only the previous two and the caller wants just the final count.

The table compares storage choices, not different answers. All three dynamic-programming forms use the same recurrence. The recursive version without memoization can revisit the same smaller inputs along many branches, so it is a poor choice when n grows.

Edge Cases and Integer Limits

Check the problem’s input contract before using the function in a judge or service. The code handles zero as one empty arrangement and rejects negative n. A judge may constrain n to a smaller positive range.

• For n = 0, the result is 1 by the empty-arrangement convention.
• For n = 1, the only choice is to stay single, so the result is 1.
• For n = 2, both-single and paired give 2 ways.
• For a judge that requests an answer modulo a number, apply that exact modulus as each recurrence step is computed.

The count grows quickly, so a type that works for small examples may overflow on a larger input. This implementation uses long long and checks before calculating the next value. On overflow, it throws std::overflow_error.

If the task requires answers beyond that range, use an arbitrary-precision integer library or the modulus specified by the task rather than changing the recurrence.

A modulo version needs a precise modulus from the problem statement. Apply the remainder after the addition and multiplication at every iteration, using a type wide enough for the intermediate product or a multiplication method suited to that modulus. Returning a reduced value changes the requested result, so keep the exact-count and modulo interfaces separate.

Many programming challenges ask for a modulo result because the exact count grows rapidly. Read the output contract before choosing a type. Exact-count tasks require the full value, while residue tasks require reduction modulo the stated number.

When using a vector-based table instead, allocate n + 1 entries before indexing dp[i]. C++ vector operator[] does not check whether an index is in range, so an undersized vector can cause undefined behavior. The rolling solution avoids indexing and also avoids allocating according to n.

Also check the input type against the task’s maximum n. The sample function accepts int, which is sufficient for the recurrence’s loop index in the shown use, but an application reading untrusted input should validate conversion and its own resource limits before calling it. A syntactically valid integer can still exceed the range or work budget the surrounding program intends to support.

For a judge with a stated upper bound, compare that bound with the numeric range of the chosen result type and with the expected runtime. The rolling loop uses constant memory, but it still performs one iteration per friend. Constant space does not make an impractically large n a constant-time calculation.

The checked function throws exceptions for invalid input and overflow. A command-line program can catch those exceptions and print a user-facing error, while an online judge may require a different interface such as returning a modulo value. Keep the recurrence separate from that interface decision so the counting logic remains clear.

g++ -std=c++17 -Wall -Wextra -pedantic friends_pairing.cpp -o friends_pairing
./friends_pairing

Conclusion

The key step is fixing one friend: they are single, or they choose one of n − 1 partners. That yields f(n) = f(n − 1) + (n − 1)f(n − 2), and two saved counts are enough to calculate the answer.

For related implementation details, see the C++ vector element access reference and numeric_limits reference. They explain the bounds-checking and integer-range details that matter when adapting a DP solution.

FAQ

These answers cover common boundary and optimization questions for this recurrence.