77. 组合

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：

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

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

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

解法一：回溯

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func combine(n int, k int) [][]int {
    var ans [][]int
    var tmp []int
    var backtracking func(cur int)
    backtracking = func(cur int) {
        if len(tmp)+(n-cur+1) < k {
            return
        }
        if len(tmp) == k {
            replica := make([]int, len(tmp))
            copy(replica, tmp)
            ans = append(ans, replica)
            // You cannot replace the above three lines with the following two lines
            // ans = append(ans, []int{})
            // copy(ans[len(ans)-1], tmp)
            return
        }
        if cur == n+1 {
            return
        }
        tmp = append(tmp, cur)
        backtracking(cur + 1)
        tmp = tmp[:len(tmp)-1]
        backtracking(cur + 1)
    }
    backtracking(1)
    return ans
}

注意: 不能使用

1
2


ans = append(ans, []int{})
copy(ans[len(ans)-1], tmp)

替换

1
2
3


replica := make([]int, len(tmp))
copy(replica, tmp)
ans = append(ans, replica)

因为 copy(dst, src []Type) int 这个内置函数的复制逻辑是：复制源切片从下标 0 开始的 x 个数据到 dst，其中 x = min(len(dst), len(src))，返回 x，下面是 copy(dst, src []Type) int 的官方说明：

// The copy built-in function copies elements from a source slice into a

// destination slice. (As a special case, it also will copy bytes from a

// string to a slice of bytes.) The source and destination may overlap. Copy

// returns the number of elements copied, which will be the minimum of

// len(src) and len(dst).