### Problem

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

### Example

If n = 4 and k = 2, a solution is:

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

### JavaScript Code

```function combine(n, k) {
var result = [];

//illegal case
if (k > n) {
return null;
//if k==n
} else if (k == n) {
var temp = [];
for (var i = 1; i <= n; i++) {
temp.push(i);
}
result.push(temp);
return result;
//if k==1
} else if (k == 1) {

for (var i = 1; i <= n; i++) {
var temp = [];
temp.push(i);
result.push(temp);
}

return result;
}

//for normal cases, initialize a list with one element
for (var i = 1; i <= n - k + 1; i++) {
var temp = [];
temp.push(i);
result.push(temp);
}

return combineHelper(n, k, result);
}

function combineHelper(n, k, result) {

var prevResult = result.slice();

if(result[0].length == k) return result;

result = [];
for (var j=0; j<prevResult.length; j++) {
var one = prevResult[j];
for (var i = 1; i <= n; i++) {
if (i > one[one.length - 1]) {
var temp = one.slice();
temp.push(i);
result.push(temp);
}
}
}

return combineHelper(n, k, result);
}
```

### Using Depth First Search

```var result = [];

function combine(n, k) {
if (n <= 0 || n < k)
return result;

var item = [];
dfs(n, k, 1, item); // because it need to begin from 1
}

function dfs(n, k, start, item) {
if (item.length == k) {
result.push(item.slice());
return;
}

for (var i = start; i <= n; i++) {
item.push(i);
dfs(n, k, i + 1, item);
item.pop();
}
}
```

#### 1 comment:

1. 123betting thanks for the code It is very helpful to me. https://www.123betting.org/