Leetcode 组合

embedded/2024/11/26 17:31:04/

在这里插入图片描述

使用回溯来解决此问题。

提供的代码使用了回溯法(Backtracking),这是一种通过递归探索所有可能解的算法思想。以下是对算法思想的详细解释:


核心思想:

回溯法通过以下步骤解决问题:

  1. 路径选择:从当前状态出发,尝试所有可能的选项。
  2. 递归探索:对当前路径进行扩展,继续深入递归以构建更长的路径。
  3. 回退:如果当前路径无法满足条件(如达到目标长度 k 或已遍历完所有可能性),撤销最后的选择并回退到上一步,尝试其他选项。

在这道题中:

  • 问题目标:生成从 1n 中长度为 k 的所有组合。
  • 递归逻辑:逐步选择当前范围内的数字,扩展路径,直到路径长度为 k
  • 回溯逻辑:在递归返回时,撤销选择以尝试其他可能性。

代码逐步解析:

  1. 初始化结果集

    List<List<Integer>> result = new ArrayList<>();
    

    result 用于存储最终的所有组合结果。

  2. 调用回溯函数

    backtrack(result, new ArrayList<>(), n, k, 1);
    
    • result 是存储结果的容器。
    • tempList 是当前路径,用于记录正在构建的组合。
    • nk 是题目中给定的参数。
    • start 是当前搜索的起始数字,避免重复选择。
  3. 回溯函数的核心逻辑

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {if (tempList.size() == k) {result.add(new ArrayList<>(tempList));return;}for (int i = start; i <= n; i++) {tempList.add(i);backtrack(result, tempList, n, k, i + 1);tempList.remove(tempList.size() - 1);}
    }
    
    • 递归终止条件

      if (tempList.size() == k) {result.add(new ArrayList<>(tempList));return;
      }
      

      如果当前路径 tempList 的长度达到了 k,将其加入结果集并停止进一步递归。

    • 循环遍历生成路径

      for (int i = start; i <= n; i++) {tempList.add(i); // 选择当前数字backtrack(result, tempList, n, k, i + 1); // 递归,向前扩展路径tempList.remove(tempList.size() - 1); // 撤销选择,回溯
      }
      

      每次选择当前数字 i,然后递归地选择下一个数字(从 i + 1 开始,避免重复)。递归返回后,撤销上一步的选择(即回退一步),尝试其他数字。

  4. 主函数调用

    System.out.println(solution.combine(4, 2)); // 示例1输出
    System.out.println(solution.combine(1, 1)); // 示例2输出
    

    打印从 1n 中长度为 k 的所有组合。


算法的时间复杂度分析

  • 状态空间:从 n 个数字中选出 k 个的所有组合,状态空间大小为 ( C(n, k) = \frac{n!}{k!(n-k)!} )。
  • 复杂度
    • 回溯会遍历所有可能的组合,每次生成一个组合需要 ( O(k) ) 的时间来构建路径。
    • 因此,总时间复杂度为 ( O(k \cdot C(n, k)) )。

算法的优点:

  • 高效性:只生成符合条件的路径,避免无效的路径探索。
  • 可扩展性:可用于解决类似的组合问题,如排列、子集等。

代码运行过程示例:

n = 4, k = 2 为例:

  1. 初始调用 backtrack([], 1)
  2. 递归过程中:
    • 选择 1,递归调用 backtrack([1], 2)
    • 在选择 1 的基础上,依次选择 234,生成组合 [1, 2][1, 3][1, 4]
    • 回退到空路径后,选择 2,依次选择 34,生成 [2, 3][2, 4]
    • 继续回退后,选择 3,选择 4,生成 [3, 4]
  3. 最终结果为:
    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    
class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), n, k, 1);return result;}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {if(tempList.size() == k) {result.add(new ArrayList<>(tempList));return;}//从start开始遍历, 生成所有可能的组合for(int i = start; i <= n; i++) {tempList.add(i);backtrack(result, tempList, n, k, i + 1); //递归生成下一层tempList.remove(tempList.size() - 1);//撤销上次的选择,tempList.size() - 1应该是元素下标}}
}

http://www.ppmy.cn/embedded/140672.html

相关文章

51单片机-独立按键与数码管联动

独立键盘和矩阵键盘检测原理及实现 键盘的分类&#xff1a;编码键盘和非编码键盘 键盘上闭合键的识别由专用的硬件编码器实现&#xff0c;并产生键编码号或键值的称为编码键盘&#xff0c;如&#xff1a;计算机键盘。靠软件编程识别的称为非编码键盘&#xff1b;在单片机组成…

享元模式 (Flyweight Pattern)

享元模式 (Flyweight Pattern) 享元模式是一种 结构型设计模式&#xff0c;通过共享相同对象&#xff0c;减少内存使用&#xff0c;提升系统性能。该模式适用于大量相似对象的场景&#xff0c;能有效避免重复创建相同对象。 原理 核心思想&#xff1a; 将对象的 内在状态&…

【C++】深入哈希表核心:从改造到封装,解锁 unordered_set 与 unordered_map 的终极奥义!

文章目录 修改哈希表模板参数迭代器HashTable 的默认成员函数HashTable 迭代器相关函数HashTable 的 Insert 函数HashTable 的 Find函数HashTable 的 Erase函数 封装 unordered_set封装 unordered_map测试 unordered_set 和 unordered_map 修改哈希表 我们基于链地址法实现的哈…

虚拟浏览器可以应对哪些浏览器安全威胁?

众所周知&#xff0c;互联网安全对企业和个人都至关重要。 因此&#xff0c;在有害的网络内容和终端用户之间必须有一道屏障。浏览器隐私是浏览器安全的一个重要组成部分。不用说也知道&#xff0c;大多数常用的浏览器&#xff0c;都会把最终用户的数据出售给第三方&#xff0c…

git教程

文章目录 简介&#xff1a;使用教程&#xff1a;&#xff08;1&#xff09;安装git&#xff1a;&#xff08;2&#xff09;设置用户名和邮箱作为标识符&#xff1a;&#xff08;3&#xff09;建立本地仓库&#xff1a;本地仓库作用&#xff1a;&#xff08;1&#xff09;将文件…

springboot获取配置文件中的值

概括 在开发过程中&#xff0c;对于一些通用的配置&#xff0c;通常会定在一个配置文件中。通常为application.properties或者application.yml文件中。我们只需要在需要使用的地方通过注解直接获取即可。 使用 在springboot中可以通过使用value注解来读取配置文件中的属性。…

随手记:鼠标触顶方法

// 鼠标触顶方法 scrollMethod() { window.onscroll () > { let t document.documentElement.scrollTop || document.body.scrollTop; if(t > 10) { this.positionStyle.top 0px; }else{ this.positionStyle.top 128px; } } },

Spring Boot OA:企业办公自动化的高效路径

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了企业OA管理系统的开发全过程。通过分析企业OA管理系统管理的不足&#xff0c;创建了一个计算机管理企业OA管理系统的方案。文章介绍了企业OA管理系统的系统分析部…