当前位置: 首页 > article >正文

Leetcode 40. 组合总和 II

 这题是LCR 083. 全排列题目上的进阶变形,需要在原来的深度优先搜索上进行剪枝来进行优化,满足题目要求。主要思路就是:搜索每一种情况,并且通过剪枝优化来去掉重复的情况和不满足的情况。以下是我的代码:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans= []
        candidates.sort()
        def dfs(start: int, s: int, path: List[int]):
            if s == target:
                ans.append(list(path))
                return
            if s > target:
                return
            for i in range(start, len(candidates)):
                if candidates[i] > target:
                    break
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                dfs(i + 1, s + candidates[i], path)
                path.pop()
        dfs(0, 0, [])
        return ans

C++:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        // 剪纸1:排序
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        vector<bool> vis(candidates.size(), false);
        function<void(int, int)> dfs = [&](int start, int sum) {
            // 找到一种情况
            if (sum == target) {
                ans.push_back(path);
                return;
            }
            if (sum > target) return;
            for (int i = start; i < candidates.size(); i ++) {
                if (candidates[i] > target) {
                    break;
                }
                // 这个剪枝很重要,避免重复的子集
                if (i > start &&  candidates[i] == candidates[i - 1]) {
                    continue;
                }
                path.push_back(candidates[i]);
                // dfs(start + 1, sum + candidates[i])
                dfs(start + 1, sum + candidates[i]);
                path.pop_back();
            }
        };
        dfs(0, 0);
        return ans;
    }
};

接下来讲解一些剪枝的作用:

剪枝1:

如果此时总和已经超过target了,那么就直接返回!!!

剪枝2:

这个剪枝相当重要,并且不易想到。去掉重复的子集!!!!

剪枝3:

和剪枝1大同小异,如果总和超过了就不需要再往下进行搜索了!!!!

剪枝4:

要从i + 1开始,如果不小心写成了 start + 1(这个错误很难发现,亲身体会!!!),那就会多出很多重复的集合(虽然顺序不一样)。

到这里就差不多结束啦!!加油!!

会持续更新!!!


http://www.kler.cn/a/526624.html

相关文章:

  • 【C++】类和对象
  • Vue.js路由管理与自定义指令深度剖析
  • chrome源码剖析—进程通信
  • 留学生scratch计算机haskell函数ocaml编程ruby语言prolog作业VB
  • 5.桥模式(Bridge)
  • 商密测评题库详解:商用密码应用安全性评估从业人员考核题库详细解析(9)
  • 我的AI工具箱Tauri+Django内容生产介绍和使用
  • Day28(补)-【AI思考】-AI会不会考虑自己的需求?
  • MathType下载与安装详细教程
  • Attention--人工智能领域的核心技术
  • PostgreSQL 插入、选择、更新、删除数据
  • Python | Pytorch | 什么是 Inplace Operation(就地操作)?
  • 前端开发之jsencrypt加密解密的使用方法和使用示例
  • 【以音频软件FFmpeg为例】通过Python脚本将软件路径添加到Windows系统环境变量中的实现与原理分析
  • nodeJS 系统学习-章节3-文件系统
  • vue3的路由配置
  • AI常见的算法和例子
  • IP服务模型
  • LeetCode - #194 Swift 实现文件内容转置
  • Java基础知识总结(三十二)--API--- java.lang.Runtime
  • 【算法设计与分析】实验2:递归与分治—Hanoi塔、棋盘覆盖、最大子段和
  • 机器学习(三)
  • kaggle视频追踪NFL Health Safety - Helmet Assignment
  • 【C++】stack与queue的模拟实现(适配器)
  • Deepseek本地部署(ollama+open-webui)
  • Spring Boot深度开发实践:从高效开发到生产级部署