In a previous post, I discussed an algorithm to generate permutations using Typescript. Today I will show a similar idea to generate combinations.

### Theory

Combinations are a way to count the number of ways to choose a subset of items from a larger set, where the order of selection does not matter. Combinations are used to solve problems related to permutations, where the order of selection does matter, **by eliminating the permutations that represent the same combination.**

Let's consider the colors Red, Green, and Blue.

If we want to find the **permutation** of this set, we will have:

Red, Green, Blue

Red, Blue, Green

Green, Red, Blue

Green, Blue, Red

Blue, Red, Green

Blue, Green, Red

However, if we want to find the **combination** of the set, we will have:

Red, Green

Red, Blue

Green, Blue

Then, as I said previously, combinations eliminate permutations that have the same subset elements, it doesn't consider the order of elements in the subset.

The formula to calculate the possible combinations of a subset is:

$$nCr = {n!\over(n-r)!r!}$$

### The Code

```
function combinations<T>(items: T[], size: number = items.length): T[][] {
const combinations: T[][] = [];
const stack: number[] = [];
let i = 0;
size = Math.min(items.length, size);
while (true) {
if (stack.length === size) {
combinations.push(stack.map((index) => items[index]));
i = stack.pop()! + 1;
}
if (i >= items.length) {
if (stack.length === 0) {
break;
}
i = stack.pop()! + 1;
} else {
stack.push(i++);
}
}
return combinations;
}
console.log(combinations([1,2,3]))
console.log(combinations([1,2,3], 2))
```

In this approach, we use a stack to keep track of the indices of the items that are currently included in the combination being built. We start by initializing the stack and setting the initial index `i`

to 0.

We use a while loop that continues until we have processed all possible combinations. Inside the loop, we have three main conditions:

If the stack length is equal to the desired size, it means we have a complete combination. We map the indices in the stack to their corresponding items in the

`items`

array and add the combination to the`combinations`

array. Then, we pop the top index from the stack and increment`i`

to the next index.If

`i`

is greater than or equal to the length of the`items`

array, it means we have reached the end and need to backtrack. If the stack length is 0, it indicates that we have processed all combinations and can exit the loop. Otherwise, we pop the top index from the stack and set`i`

to the next index.If none of the above conditions are met, it means we can add the current index

`i`

to the stack and increment`i`

to the next index.

By iterating through these conditions, we build the combinations iteratively and add them to the `combinations`

array. Finally, we return the `combinations`

array as the output.

**Conclusion**

In this post, we used an auxiliary stack to help us to find the combinations of an array in Typescript. Frequently I use it to generate variations of a given input. The idea presented here can be applied in any programming language. Combinations are an interesting field in mathematics and they are very helpful in computation.