Ball and Box: Two Perspectives of Backtracking Enumeration

Before diving into this article, you need to be familiar with the Backtracking Algorithm Core Framework and Backtracking Algorithm to Solve All Permutations/Combinations/Subsets.

In these two articles, readers have suggested different ways to write permutation/combination/subset code, such as using swap to achieve full permutations and subset solutions without for loops. I previously avoided discussing these alternative methods to maintain consistency in problem-solving approaches. Introducing too many options early on can be confusing.

In this article, I will not only introduce the backtracking algorithm methods I haven't covered before but also explain why they work and what the essential differences are between the two approaches.

Brute-Force Enumeration Method: The Ball and Box Model

All brute-force enumeration algorithms start with the ball and box model, without exception.

Once you understand this, you can effortlessly apply brute-force enumeration algorithms. Please read the following content carefully and think deeply.

First, let's review some previously learned knowledge about permutations and combinations:

1. P(n, k) (often written as A(n, k) in many texts) represents the total number of permutations (or arrangements) of selecting k elements from n distinct elements; C(n, k) represents the total number of combinations of selecting k elements from n distinct elements.

2. The main difference between "permutation" and "combination" is whether the order of elements is considered.

3. The formulas for calculating the total number of permutations and combinations:

Permutation P(n, k)

Now, let me ask a question: how is the permutation formula P(n, k) derived? To clarify this, I need to discuss some concepts from combinatorial mathematics.

Various variations of permutation and combination problems can be abstracted into the "ball and box model." The permutation P(n, k) can be represented by the following scenario:

That is, placing n balls, each with a different number to indicate order, into k boxes, each also numbered differently (where n >= k, and each box ends up with exactly one ball). There are P(n, k) different ways to do this.

Now, when you place balls into boxes, how would you do it? There are two perspectives to consider.

First, from the perspective of the boxes, each box must choose one ball.

In this view, the first box can choose any of the n balls, and then the remaining k - 1 boxes need to choose from the n - 1 balls left (this is the subproblem P(n - 1, k - 1)):

Alternatively, from the perspective of the balls, not every ball will be placed in a box, so there are two situations:

1. The first ball might not be placed in any box, leaving you to place the remaining n - 1 balls into k boxes.

2. The first ball could be placed in any of the k boxes, so you would then place the remaining n - 1 balls into k - 1 boxes.

Combining these two situations, we obtain:

As you can see, the two perspectives yield two different recursive formulas, but both lead to the factorial form we are familiar with:

The process of solving these recursive formulas involves more mathematical content, which we will not delve into here. Interested readers are encouraged to study combinatorial mathematics on their own.