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