## Algorithm

Problem Name: 77. 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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void bt(int *buff, int ***p, int *psz, int *pn, int n, int k, int d, int start) {
int i;
if (d == k) {
// all done
if (*psz == *pn) {
*psz *= 2;
*p = realloc(*p, *psz * sizeof(int *));
//assert(*p);
}
(*p)[*pn] = malloc(k * sizeof(int));
//assert((*p)[*pn]);
memcpy((*p)[(*pn) ++], buff, k * sizeof(int));
return;
}
for (i = start; i  < = n; i ++) {
buff[d] = i;
bt(buff, p, psz, pn, n, k, d + 1, i + 1);
}
}
int** combine(int n, int k, int** columnSizes, int* returnSize) {
int **p, *buff;
int psz, pn;

pn = 0;
psz = 10;
p = malloc(psz * sizeof(int *));
buff = malloc(k * sizeof(int));
//assert(p && buff);

bt(buff, &p, &psz, &pn, n, k, 0, 1);

free(buff);

*columnSizes = malloc(pn * sizeof(int));
//assert(*columnSizes);

*returnSize = pn;

while (pn --) {
(*columnSizes)[pn] = k;
}

return p;
}
``````
Copy The Code &

Input

cmd
n = 4, k = 2

Output

cmd
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
vector < vector<int> > combine(int n, int k) {
vector < vector<int> > ans;
vector<int> temp;

combineHelper(1, n, k, temp, ans);

return ans;
}

void combineHelper(int start, int end, int k, vector<int> &temp, vector < vector<int> > &ans) {
if (k == temp.size()) {
ans.push_back(temp);
return;
}

for (int i = start; i  < = end; i++) {
temp.push_back(i);
combineHelper(i + 1, end, k, temp, ans);
temp.pop_back();
}
}
};

int main() {
int n = 4;
int k = 2;
Solution s;
vector < vector<int> > ans = s.combine(n, k);

for (int i = 0; i  <  ans.size(); i++) {
for (int j = 0; j  <  ans[i].size(); j++) {
printf("%d ", ans[i][j]);
}
printf("\n");
}

return 0;
}
``````
Copy The Code &

Input

cmd
n = 1, k = 1

Output

cmd
[[1]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
List curr = new ArrayList<>();
helper(ans, curr, new boolean[n], k, 0);
return ans;
}

private void helper(List < List curr, boolean[] visited, int k, int idx) {
if (curr.size() == k) {
}
else {
for (int i = idx; i  <  visited.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
helper(ans, curr, visited, k, i + 1);
curr.remove(curr.size() - 1);
visited[i] = false;
}
}
}
}
``````
Copy The Code &

Input

cmd
n = 4, k = 2

Output

cmd
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const combine = function(n, k) {
const res = [];
bt(res, [], 1, n, k);
return res;
};

function bt(res, tmp, start, n, k) {
if (k === 0) {
res.push(tmp.slice(0));
return;
}
for (let i = start; i  < = n - k + 1; i++) {
tmp.push(i);
bt(res, tmp, i + 1, n, k - 1);
tmp.pop();
}
}
``````
Copy The Code &

Input

cmd
n = 1, k = 1

Output

cmd
[[1]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
bfs = [[]]
for num in range(1, n + 1):
bfs += [arr + [num] for arr in bfs if len(arr) < k]
return [arr for arr in bfs if len(arr) == k]
``````
Copy The Code &

Input

cmd
n = 1, k = 1

Output

cmd
[[1]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _077_Combinations
{
public IList < IList<int>> Combine(int n, int k)
{
if (n  < = 0 || k <= 0 || k > n) { return null; }

var results = new List();
for (i = 0; i  <  n; i++)
if (select[i]) { result.Add(i + 1); }

hasNext = false;
count = 0;
for (i = 0; i  <  n - 1; i++)
{
if (select[i] && !select[i + 1])
{
select[i + 1] = true;
select[i] = false;
hasNext = true;

for (j = 0; j  <  i; j++)
select[j] = count-- > 0 ? true : false;

break;
}

if (select[i]) { count++; }
}

if (!hasNext) break;
}

return results;
}
}
}
``````
Copy The Code &

Input

cmd
n = 1, k = 1

Output

cmd
[[1]]