Combinations

Problem Statement

Given two integers, n and k, the task is to generate all possible combinations of k numbers chosen from the set {1, 2, ..., n}. Importantly, the order of numbers within each combination does not matter. For instance, if the selected numbers are from 1 to 4 and you are choosing 2 out of them, [2,1] is the same as [1,2] and should only be considered once. This problem asks for a deep understanding of combination calculations where only unique sets of chosen numbers are returned without any order significance. It provides a way to grasp the idea of combinators in mathematical terms and explore algorithms that can handle generating these combinations efficiently.

Examples

Example 1

Input:

n = 4, k = 2

Output:

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Explanation:

There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2

Input:

n = 1, k = 1

Output:

[[1]]

Explanation:

There is 1 choose 1 = 1 total combination.

Constraints

• 1 <= n <= 20
• 1 <= k <= n

Approach and Intuition

The problem requires generating combinations, which is a fundamental task often solved using backtracking - a recursive strategy to build up solutions incrementally, removing solutions that fail to satisfy the constraints (in this case ensuring each solution is a unique combination of exactly k elements).

Given the nature of the problem, where the answer needs to include all possible unordered k-length subsets of a set that ranges from 1 to n, let's break down our approach:

1. Start with an empty list to store the combinations.
2. Use a helper function that will recursively:
   • Choose an element to add to the running combination.
   • Recurse with this new combination.
   • Backtrack by removing the recently added element and trying the next possible candidate.
3. This recursive function will iterate over the sequence from the last included element's next to n, ensuring that each combination is generated in a sorted manner (thus inherently avoiding duplicates like [2,1] when [1,2] has already been considered).
4. Once the length of the current combination reaches k, it's added to the list of completed combinations.
5. The recursion base case triggers when the combination size equals k, ensuring all combinations are of the required size.

Using this recursive backtracking approach, we ensure that:

• All combinations are explored.
• Each combination is collected in a sorted order once.
• Efficiency by backtracking early if a potential combination surpasses allowed sizes, thanks to the constraints of our problem.

Examples help in understanding the effectiveness of this method:

• For n = 4 and k = 2, the function would sequentially build combinations by starting with [1], then adding [2], checking if full [1, 2] matches k = 2, and recursively processing in a similar fashion for [1, 3], [1, 4], and so on, for embeddings like [2, 3], [3, 4] without ever reusing numbers.
• The enumeration is controlled and does not repeat due to the ordered additions and the base case check that halts deeper recursions when k size is achieved.

By managing the depth of recursion and ensuring selected numbers are only advanced forward, the method can effectively generate orderly combinations without redundancy. Thus, it cleverly navigates the exponential nature of combination problems within given constraints.

Solutions

class Solution {
public:
    int comboLength;
    int setLimit;
    
    vector<vector<int>> generateCombinations(int setLimit, int comboLength) {
        this->comboLength = comboLength;
        this->setLimit = setLimit;
        vector<vector<int>> result;
        vector<int> combination;
        findCombinations(combination, 1, result);
        return result;
    }
    
    void findCombinations(vector<int>& combination, int start, vector<vector<int>>& result) {
        if (combination.size() == comboLength) {
            result.push_back(combination);
            return;
        }
    
        int needed = comboLength - combination.size();
        int left = setLimit - start + 1;
        int maxReach = left - needed;
    
        for (int value = start; value <= start + maxReach; value++) {
            combination.push_back(value);
            findCombinations(combination, value + 1, result);
            combination.pop_back();
        }
    }
};