Question

剑指 Offer II 080. 含有 k 个元素的组合

题目描述

给定两个整数 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 题相同： https://leetcode.cn/problems/combinations/

解法

方法一

class Solution:
  def combine(self, n: int, k: int) -> List[List[int]]:
    res = []

    def dfs(i, n, k, t):
      if len(t) == k:
        res.append(t.copy())
        return
      for j in range(i, n + 1):
        t.append(j)
        dfs(j + 1, n, k, t)
        t.pop()

    dfs(1, n, k, [])
    return res

class Solution {
  public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(1, n, k, new ArrayList<>(), res);
    return res;
  }

  private void dfs(int i, int n, int k, List<Integer> t, List<List<Integer>> res) {
    if (t.size() == k) {
      res.add(new ArrayList<>(t));
      return;
    }
    for (int j = i; j <= n; ++j) {
      t.add(j);
      dfs(j + 1, n, k, t, res);
      t.remove(t.size() - 1);
    }
  }
}

class Solution {
public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> t;
    dfs(1, n, k, t, res);
    return res;
  }

  void dfs(int i, int n, int k, vector<int> t, vector<vector<int>>& res) {
    if (t.size() == k) {
      res.push_back(t);
      return;
    }
    for (int j = i; j <= n; ++j) {
      t.push_back(j);
      dfs(j + 1, n, k, t, res);
      t.pop_back();
    }
  }
};

func combine(n int, k int) [][]int {
  var res [][]int
  var t []int
  dfs(1, n, k, t, &res)
  return res
}

func dfs(i, n, k int, t []int, res *[][]int) {
  if len(t) == k {
    *res = append(*res, slices.Clone(t))
    return
  }
  for j := i; j <= n; j++ {
    t = append(t, j)
    dfs(j+1, n, k, t, res)
    t = t[:len(t)-1]
  }
}