77-组合.md

题目描述

组合

题目简述

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

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

示例 1：

• 输入：n = 4, k = 2
• 输出： [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

分类

中等 数组 回溯

思路

思路1

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const res = []
  function backTrack (index, arr) {
    if (arr.length === k) {
      res.push([...arr])
      return
    }
    for(let i = index; i <= n; i++) {
      arr.push(i)
      backTrack(i + 1, arr)
      arr.pop()
    }
  }
  backTrack(1, [])
  return res
};

• 问题分析
  • 因为要寻找的结果数组长度为k，是不定的，所以我们通过对[1, n]递归，将数字填入结果数组中。
  • backTrack作用：遍历从index到n的数，这些都是当前可以填充的数据，填入结果数组后进行递归调用，然后将该位换为下一个数。
  • 回溯终止条件：结果数组长度等于预期的k
  • 回溯可能性：[index, n]