---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20080.%20%E5%90%AB%E6%9C%89%20k%20%E4%B8%AA%E5%85%83%E7%B4%A0%E7%9A%84%E7%BB%84%E5%90%88/README.md

剑指 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/

解法

方法一

Python3

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:res=[]path=[]def dfs(i):if len(path)==k:res.append(path[:])returnfor j in range(i,n+1): #层选法path.append(j)dfs(j+1)path.pop()dfs(1)return res

Java

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);}}
}

C++

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();}}
};

Go

func combine(n int, k int) [][]int {var res [][]intvar t []intdfs(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]}
}

Swift

class Solution {func combine(_ n: Int, _ k: Int) -> [[Int]] {var res = [[Int]]()dfs(1, n, k, [], &res)return res}private func dfs(_ start: Int, _ n: Int, _ k: Int, _ current: [Int], _ res: inout [[Int]]) {if current.count == k {res.append(current)return}if start > n {return}for i in start...n {var newCurrent = currentnewCurrent.append(i)dfs(i + 1, n, k, newCurrent, &res)}}
}