Combinations Leetcode Solution

In this post, we are going to solve the Combinations Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of Contents

Problem

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

Now, let’s see the leetcode solution of Combinations Leetcode Solution.

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

Combinations Leetcode Solution in CPP

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, move(path), ans);
      path.pop_back();
    }
  }
};

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);
    }
  }
}

Note: This problem Combinations is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

NEXT: Subsets Leetcode Solution