dw做网站的搜索栏怎么做,个人网页设计硬件需求,广州商旅网站制作,网站变黑白代码组合
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1#xff1a;
输入#xff1a; n 4, k 2 输出#xff1a; [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
解题思路
定义递归函数#xff1…组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入 n 4, k 2 输出 [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
解题思路
定义递归函数定义一个递归函数 backtrack 用来生成组合。递归终止条件如果当前组合的长度达到 k将其添加到结果列表中。选择元素从当前起始元素到 n 进行迭代选择每个元素加入当前组合。递归调用选择元素后递归调用函数生成下一个元素的组合。回溯在递归完成后移除当前选择的元素尝试选择下一个元素。
Java实现
public class Combine {public ListListInteger combine(int n, int k) {ListListInteger res new ArrayList();backtrack(1, n, k, new ArrayList(), res);return res;}private void backtrack(int start, int n, int k, ListInteger path, ListListInteger res) {// 如果组合完成if (path.size() k) {res.add(new ArrayList(path));return;}// 从start到n遍历所有的数字for (int i start; i n; i) {// 将i添加到当前组合path.add(i);// 使用下一个整数完成组合backtrack(i 1, n, k, path, res);// 回溯通过移除ipath.remove(path.size() - 1);}}// 测试用例public static void main(String[] args) {Combine solution new Combine();System.out.println(solution.combine(4, 2)); // 期望输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]System.out.println(solution.combine(5, 3)); // 期望输出: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]}
}
时间空间复杂度
时间复杂度O(C(n, k) * k)其中 C(n, k) 是从 n 个数中选 k 个数的组合数。生成每个组合需要 O(k) 的时间。空间复杂度O(k)递归栈的深度最多为 k存储当前组合的路径 path 也需要 O(k) 的空间。
