CODEWITHSUNDEEP
javarecursioncombinationspermutationmathematical-expressions
Ankush Dutt
Ankush Dutt

Reputation: 133

Understanding recursion using all possible combinations in an array

I'm trying to understand recursion with the help of few examples. I found this example of printing all possible combinations of r elements in a given array of size n using recursion.

Print all possible combinations of r elements in a given array of size n.

They are using the idea behind the expression:

enter image description here

What i'm trying to understand here is the conceptual meaning of this expression. I have read different articles but couldn't find a satisfactory explanation.

A mathematical or practical example which uses this expression would be really helpful.

Upvotes: 1

Views: 114

Answers (1)

MarianD
MarianD

Reputation: 14191

First, there are different notations for combinations in math:

enter image description here

Using the first of them, your formula is

enter image description here

The left-hand side of it means: The number of ways we can select r elements from the set of n elements.

Let S be a set of n elements. Let x be the last element of it, so the set S is for example

+-------------+---+
| a b c d e f | x |
+-------------+---+

Let C is an arbitrary combination of r elements from the set S.

(Particularly, to follow just introduced example, you may imagine that r = 3, and n = 7 - as the set is {a, b, c, d, e, f, x}.)

There are only 2 possibilities:

  1. C contains x (e. g. C = {a, d, x}), or
  2. C does not contain x (e. g. C = {a, d, e}).

If C contains x, then remaining (r - 1) elements (i. e. 2 in our example) are chosen from remaining (n - 1) elements (i. e. from {a, b, c, d, e, f} in our example) - so there are

enter image description here

ways how to select such combination.

If C does not contain x, then all r elements are chosen from remaining (n - 1) elements - so there are

enter image description here

ways how to select such combination.

Upvotes: 2

Related Questions