题目

给定两个整数 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

注意：本题与主站 77 题相同：

解题思路分析

1、回溯；时间复杂度O(kC(n,k))，空间复杂度O(C(n,k))

var res [][]int

func combine(n int, k int) [][]int {
   res = make([][]int, 0)
   nums := make([]int, 0)
   for i := 1; i <= n; i++ {
      nums = append(nums, i)
   }
   dfs(nums, 0, k)
   return res
}

func dfs(nums []int, index, k int) {
   if index == k {
      temp := make([]int, k)
      copy(temp, nums[:k])
      res = append(res, temp)
      return
   }
   for i := index; i < len(nums); i++ {
      if index == 0 || nums[i] > nums[index-1] {
         nums[i], nums[index] = nums[index], nums[i]
         dfs(nums, index+1, k)
         nums[i], nums[index] = nums[index], nums[i]
      }
   }
}

2、回溯；时间复杂度O(kC(n,k))，空间复杂度O(C(n,k))

var res [][]int

func combine(n int, k int) [][]int {
   res = make([][]int, 0)
   dfs(n, k, 1, make([]int, 0))
   return res
}

func dfs(n, k, index int, arr []int) {
   if len(arr) == k {
      temp := make([]int, k)
      copy(temp, arr)
      res = append(res, temp)
      return
   }
   for i := index; i <= n; i++ {
      arr = append(arr, i)
      dfs(n, k, i+1, arr)
      arr = arr[:len(arr)-1]
   }
}

3、回溯；时间复杂度O(kC(n,k))，空间复杂度O(C(n,k))

var res [][]int

func combine(n int, k int) [][]int {
   res = make([][]int, 0)
   nums := make([]int, 0)
   for i := 1; i <= n; i++ {
      nums = append(nums, i)
   }
   dfs(nums, 0, k, make([]int, 0))
   return res
}

func dfs(nums []int, index, k int, arr []int) {
   if len(arr) == k {
      temp := make([]int, k)
      copy(temp, arr)
      res = append(res, temp)
      return
   }
   for i := index; i < len(nums); i++ {
      arr = append(arr, nums[i])
      dfs(nums, i+1, k, arr)
      arr = arr[:len(arr)-1]
   }
}

4、迭代；时间复杂度O(kC(n,k))，空间复杂度O(C(n,k))

func combine(n int, k int) [][]int {
   res := make([][]int, 0)
   arr := make([]int, 0)
   for i := 1; i <= k; i++ {
      arr = append(arr, 0)
   }
   i := 0
   for i >= 0 {
      arr[i]++
      if arr[i] > n {
         i--
      } else if i == k-1 {
         temp := make([]int, k)
         copy(temp, arr)
         res = append(res, temp)
      } else {
         i++
         arr[i] = arr[i-1]
      }
   }
   return res
}

5、回溯；时间复杂度O(kC(n,k))，空间复杂度O(C(n,k))

var res [][]int

func combine(n int, k int) [][]int {
   res = make([][]int, 0)
   dfs(n, k, 1, make([]int, 0))
   return res
}

func dfs(n, k, index int, arr []int) {
   if index > n+1 {
      return
   }
   if len(arr) == k {
      temp := make([]int, k)
      copy(temp, arr)
      res = append(res, temp)
      return
   }
   dfs(n, k, index+1, arr)
   arr = append(arr, index)
   dfs(n, k, index+1, arr)
}

总结

Medium题目，题目同leetcode 77.组合