# 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.

## 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: []
Explanation: There is 1 choose 1 = 1 total combination.
```

Constraints:

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

Now, lets 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
```

### CombinationsLeetcode Solutionin 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();
}
}
};
```

### CombinationsLeetcode 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) {
return;
}

for (int i = s; i <= n; ++i) {