77. Combinations

Description

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

Intuition

The problem requires generating all possible combinations of k numbers from a set of numbers ranging from 1 to n. This can be efficiently achieved using a backtracking approach, which explores all potential combinations and backtracks when a solution or a dead-end is reached.

Approach

1. Initialize a Result List: Start with an empty list to store all valid combinations.
2. Backtracking Function: Define a helper function backtrack that takes the current starting index and the current combination as parameters. - Base Case: If the length of the current combination equals k, add it to the result list. - Recursive Case: Iterate over the numbers from the current start index to n, add each number to the current combination, and recursively call the backtrack function with the next starting index. - After the recursive call, remove the last number added to the combination to explore other possibilities.
3. Initial Call: Call the backtrack function initially with the start index 1 and an empty combination.

Complexity

Time Complexity:

(O(C(n, k) \cdot k)), where (C(n, k)) is the binomial coefficient representing the number of combinations. Each combination is constructed in (O(k)) time.

Space Complexity:

(O(C(n, k) \cdot k)), which accounts for the space needed to store all combinations. The recursive stack space is (O(k)).

Code

C++

class Solution {
public:
    vector> combine(int n, int k) {
        vector> result;
        vector combination;

        backtrack(n, k, 1, combination, result);
        return result;
    }

private:
    void backtrack(int n, int k, int start, vector& combination, vector>& result) {
        if (combination.size() == k) {
            result.push_back(combination);
            return;
        }

        for (int i = start; i <= n; ++i) {
            combination.push_back(i);
            backtrack(n, k, i + 1, combination, result);
            combination.pop_back();
        }
    }
};

Python

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(start, combination):
            if len(combination) == k:
                result.append(combination[:])
                return

            for i in range(start, n + 1):
                combination.append(i)
                backtrack(i + 1, combination)
                combination.pop()

        result = []
        backtrack(1, [])
        return result     

Java

class Solution {
    public List> combine(int n, int k) {
        List> result = new ArrayList<>();
        List combination = new ArrayList<>();
        backtrack(n, k, 1, combination, result);
        return result;
    }

    private void backtrack(int n, int k, int start, List combination, List> result) {
        if (combination.size() == k) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = start; i <= n; ++i) {
            combination.add(i);
            backtrack(n, k, i + 1, combination, result);
            combination.remove(combination.size() - 1);
        }
    }
}

JavaScript

var combine = (n, k) => 
{
  let q = [], r = []

  for(let i = 1; i <=n; i++) q.push([i])
  
  while(q.length) {
    let Q = []

    q.forEach(e => {
      if(e.length === k) return r.push(e)

      for(let i = e[e.length - 1] + 1; i <= n; i++) Q.push([...e, i])
    })

    q = Q
  }
  return r
}