algoadvance

Leetcode 77. Combinations

Problem Statement

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the combinations in any order.

Example

Input: n = 4, k = 2
Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

Clarifying Questions

1. Can n or k be zero?
   • Yes, if k is zero, the result should be an empty list within a list: [[]].
2. What are the constraints on the values of n and k?
   • Typically, 1 <= k <= n <= 20 is a reasonable assumption for combinatorial problems.
3. Are negative values allowed?
   • No, n and k are positive integers.

Strategy

1. Backtracking:
   • Use a backtracking approach to explore all possible combinations.
   • Start from the number 1 to n.
   • At each step, add the current number to the combination and recursively make combinations of the next numbers.
   • Backtrack after a recursive call, so that other combinations could be formed by removing the current number and moving to the next one.

Code

#include <vector>

class Solution {
public:
    void backtrack(int start, int n, int k, std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (current.size() == k) {
            result.push_back(current);
            return;
        }
        
        for (int i = start; i <= n; ++i) {
            current.push_back(i);
            backtrack(i + 1, n, k, current, result);
            current.pop_back(); // backtrack
        }
    }
    
    std::vector<std::vector<int>> combine(int n, int k) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(1, n, k, current, result);
        return result;
    }
};

Time Complexity

• Time Complexity: (O(C(n, k) \times k))
  • (C(n, k)) represents the number of combinations, and this is given by the binomial coefficient “n choose k”: ( \frac{n!}{k!(n-k)!} ).
  • For each combination, adding the combination to the result takes (O(k)).
• Space Complexity: (O(C(n, k) \times k))
  • This is due to the storage required for all the combinations, where there are (C(n, k)) combinations, each of size (k). Also, the recursion stack uses (O(k)) space.

By following the backtracking approach, we ensure that we explore all valid combinations efficiently while backtracking appropriately to explore other paths.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?