77. Combinations LeetCode Solution

In this guide, you will get 77. Combinations LeetCode Solution with the best time and space complexity. The solution to Combinations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Combinations solution in C++
Combinations solution in Java
Combinations solution in Python
Additional Resources

77. Combinations LeetCode Solution image

Problem Statement of Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.

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

Complexity Analysis

Time Complexity: O(C(n, k) \cdot k)
Space Complexity: O(C(n, k))

77. Combinations LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    dfs(n, k, 1, {}, ans);
    return ans;
  }

 private:
  void dfs(int n, int k, int s, vector<int>&& path, vector<vector<int>>& ans) {
    if (path.size() == k) {
      ans.push_back(path);
      return;
    }

    for (int i = s; i <= n; ++i) {
      path.push_back(i);
      dfs(n, k, i + 1, std::move(path), ans);
      path.pop_back();
    }
  }
};
/* code provided by PROGIEZ */

77. Combinations LeetCode Solution in Java

class Solution {
  public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(n, k, 1, new ArrayList<>(), ans);
    return ans;
  }

  private void dfs(int n, int k, int s, List<Integer> path, List<List<Integer>> ans) {
    if (path.size() == k) {
      ans.add(new ArrayList<>(path));
      return;
    }

    for (int i = s; i <= n; ++i) {
      path.add(i);
      dfs(n, k, i + 1, path, ans);
      path.remove(path.size() - 1);
    }
  }
}
// code provided by PROGIEZ

77. Combinations LeetCode Solution in Python

class Solution:
  def combine(self, n: int, k: int) -> list[list[int]]:
    ans = []

    def dfs(s: int, path: list[int]) -> None:
      if len(path) == k:
        ans.append(path.copy())
        return

      for i in range(s, n + 1):
        path.append(i)
        dfs(i + 1, path)
        path.pop()

    dfs(1, [])
    return ans
 # code by PROGIEZ