### 77.Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. You may return the answer in any order.

Example 1:

``````Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]``````

Example 2:

``````Input: n = 1, k = 1
Output: [[1]]``````

Constraints:

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

### analyze

n: 1, 2, 3, 4 k: 2

• 1
• 2
• 3
• 4
• 2
• 3
• 4
• 3
• 4

``````/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const result = []
backTrace(n, k, 1, [], result)
return result
};

var backTrace = function(n, k, index, temp, result) {
if (temp.length === k) {
if (ifIncrease(temp)) {
result.push([...temp])
}
return
}

for (let i = index; i <= n; i++) {
temp.push(i)
backTrace(n, k, index + 1, temp, result)
temp.pop()
}
}

var ifIncrease = function(arr) {
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] >= arr[i + 1]) return false
}
return true
}``````

``````- backTrace(n, k, index + 1, temp, result)
+ backTrace(n, k, i + 1, temp, result)``````
``````/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const result = []
backTrace(n, k, 1, [], result)
return result
};

var backTrace = function(n, k, index, temp, result) {
if (temp.length === k) {
result.push([...temp])
return
}

for (let i = index; i <= n; i++) {
temp.push(i)
backTrace(n, k, i + 1, temp, result)
temp.pop()
}
}``````

### 回溯法剪支

``````* 1
* 2
* 3
* 4
* 5
* 3
* 4
* 5
* 4
* 5
* 5 // 减支
* 2
* 3
* 4
* 5
* 4
* 5
* 5 // 减支
* 3
* 4
* 5
* 5 // 减支
* 4 // 减支``````

``````/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const result = []
backTrace(n, k, 1, [], result)
return result
};

var backTrace = function(n, k, index, temp, result) {
if (temp.length === k) {
result.push([...temp])
return
}

// 题目可以转化为从搜索上界到 n 中要取的数字长度为 (k - temp.length)。
// 可以得出搜索上界为: n - (k - temp.length) + 1
for (let i = index; i <= n - (k - temp.length) + 1; i++) {
temp.push(i)
backTrace(n, k, i + 1, temp, result)
temp.pop()
}
}``````