Combinations

This page provides links to solutions that use the combinations.

Overview

Combinations represent selections of items from larger group, where the order doesn't matter. The formula for calculating combinations is as below:

$$^\text{n}\text{C}_\text{r}= \frac{\text{n}!}{\text{r}!(\text{n}−\text{r})!}$$

Where $\text{n}$ is the total number of items, and $\text{r}$ is the number of items to choose.

How to Spot These Problems

You can identify combination problems if the problem requires you to:

• Choose a subset of items from a larger set, to make $\text{K}$ subsets.

info

All the combinations problem can also be solved using backtracking approach as well.

Think of it this way, instead of choosing a subset of item from larger set to make $\text{K}$ subsets, we can assign each element to $\text{K}$ subsets. However, if we use backtracking, time complexity of the problem becomes $\text{K}^{\text{N}}$. If $\text{K}$ is too large, this would lead to time limit exceeded exception.

To avoid this, we use combinatorial approach, where we first generate single subset, which has time complexity of $2^\text{N}$, as for for each element there only two options: it can either be part of subset or not. Given that we need to generate $\text{K}$ such subsets, the total time complexity becomes $\text{K} * 2^\text{N}$.

Leetcode Problem Set

# ▲	Solution
698	Partition to K Equal Sum Subsets

Total Solved: 1