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:
Where is the total number of items, and 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 subsets.
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 subsets, we can assign each element of set to subsets. However, if we use backtracking, time complexity of the problem becomes . If is too large, this would lead to time limit exceed exception.
To avoid this, we use combinatorial approach, where we first generate single subset from larger set which takes time complexity of . Given that we need to generate such subsets, the total time complexity becomes .
Leetcode Problem Set
# ▲ | Solution |
---|---|
698 | Partition to K Equal Sum Subsets |