组合

Tips

题目类型: BackTracking

题目

给定两个整数 n 和 k, 返回 1 ... n 中所有可能的 k 个数的组合.

提示:

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

示例

输入: n = 4, k = 2

输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]

题解

这个题其实是 40. 组合总数 II 的变体. 翻译过来就是: 候选项为[1, n], 每个组合有 k 个数, 每个数字只能选一次, 且组合不能重复(即 [1, 2] 和 [2, 1] 视为同一个).

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const res = []

  const dfs = function (begin, track) {
    if (track.length === k) {
      res.push(track)
      return
    }

    for (let i = begin; i <= n; i++) {
      if (!track.includes(i)) {
        track.push(i)
        dfs(i, track.slice())
        track.pop()
      }
    }
  }

  dfs(1, [])
  return res
}

Rust

pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut res: Vec<Vec<i32>> = vec![];
    dfs(1, n as usize, k as usize, &mut vec![], &mut res);
    res
}

fn dfs(begin: usize, n: usize, k: usize, track: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
    if track.len() == k {
        res.push(track.to_vec());
        return;
    }

    for i in begin..=n {
        if !track.contains(&(i as i32)) {
            track.push(i as i32);
            dfs(i, n, k, track, res);
            track.pop();
        }
    }
}