39. 组合总和,40.组合总和II,131.分割回文串

简介: 1. **组合总和**(LeetCode 39):从无重复元素的整数数组中选取任意数量的数字,使其和等于目标值。允许重复选取同一数字,通过递归与回溯实现。2. **组合总和 II**(LeetCode 40):在含有重复元素的数组中选取数字,满足和为目标值,每个数字只能使用一次,需去重。3. **分割回文串**(LeetCode 131):将字符串分割为多个子串,要求每个子串都是回文串,返回所有可能的分割方案。代码实现中运用了深度优先搜索(DFS)、回溯法以及剪枝技巧,确保高效解决问题。

 题目:39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。  

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates =  

[2,3,6,7],  

target =  

7

输出:[[2,2,3],[7]]

解释:

2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。

7 也是一个候选, 7 = 7 。

仅有这两种组合。

示例 2:

输入: candidates = [2,3,5]

,  

target = 8

输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates =  

[2],  

target = 1

输出: []

提示:

1 <= candidates.length <= 30

2 <= candidates[i] <= 40

candidates 的所有元素 互不相同

1 <= target <= 40

思考历程与知识点:  

题目中的无限制重复被选取,吓得我赶紧想想 出现0 可咋办,然后看到下面提示:1 <= candidates[i] <= 200,我就放心了。

本题和77.组合  、216.组合总和III 的区别是:本题没有数量要求,可以无限重复,但是有总和的限制,所以间接的也是有个数的限制。

单层for循环依然是从startIndex开始,搜索candidates集合。

题解:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.push_back(path);
            return;
        }
 
        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1了,表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

 题目:40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。  

示例 1:

输入: candidates =  

[10,1,2,7,6,1,5]

, target =  

8

,

输出:

[

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,

输出:

[

[1,2,2],

[5]

]

提示:

1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

思考历程与知识点:  

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false,就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

题解:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false,说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1,这里是i+1,每个数字在每个组合中只能使用一次
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }
 
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先把给candidates排序,让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};

 题目:131. 分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"

输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"

输出:[["a"]]

提示:

1 <= s.length <= 16

s 仅由小写英文字母组成

思考历程与知识点:  

本题这涉及到两个关键问题:

切割问题,有不同的切割方式

判断回文

全局变量数组path存放切割后回文的子串,二维数组result存放结果集。 (这两个参数可以放到函数参数里)

本题递归函数参数还需要startIndex,因为切割过的地方,不能重复切割,和组合问题也是保持一致的。

题解:

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path; // 放已经回文的子串
    void backtracking (const string& s, int startIndex) {
        // 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome(s, startIndex, i)) {   // 是回文子串
                // 获取[startIndex,i]在s中的子串
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {                                // 不是回文,跳过
                continue;
            }
            backtracking(s, i + 1); // 寻找i+1为起始位置的子串
            path.pop_back(); // 回溯过程,弹出本次已经填在的子串
        }
    }
    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};


相关文章
|
11月前
|
缓存 网络协议 BI
阿里云云解析DNS个人版19.9元值得买,功能及特性介绍
阿里云DNS云解析个人版限时优惠19.9元/年(原价48元),全球100+节点,支持DNSSEC、智能解析、URL转发等功能,解析稳定快速,仅限个人开发者购买,限购1个,性价比高,值得入手。
1112 15
|
Java 开发者 微服务
Java企业应用软件系统架构演变史
Java企业应用软件系统架构演变史
513 0
|
负载均衡 算法 数据安全/隐私保护
|
人工智能 自然语言处理 Apache
有哪些类似 Danswer 的开源问答系统?
本文介绍了五款开源问答系统:Apache Answer适合团队知识沉淀;QAnything可将杂乱文档变为可对话的知识库;Haystack适合作为企业级问答中台基础;KoalaQA聚焦售后与智能客服场景;Khoj则是个人AI知识助手。选择时需根据使用场景、技术投入与团队需求匹配,系统落地后更需持续运营才能真正发挥作用。
693 0
|
7月前
|
存储 人工智能 自然语言处理
阿里云部署 Hermes Agent/OpenClaw及使用从入门到精通:必装Skill+几个实战案例
OpenClaw的革命性在于将AI从“内容生成工具”升级为“自动化执行代理”,通过自托管部署、丰富的Skill生态、多平台联动,实现了“想法即成果”的高效闭环。从阿里云15分钟快速部署,到3大必装Skill解锁核心功能,再到30天系统学习与实战落地,新手可逐步掌握其核心用法。
1340 1
|
7月前
|
弹性计算 人工智能 小程序
阿里云ECS云服务器部署 OpenClaw 图文步骤:微信小程序集成+千问Qwen3.6-Plus配置+避坑指南
2026年,OpenClaw(原Clawdbot)作为开源AI代理自动化框架的标杆产品,凭借轻量化部署、跨平台兼容、大模型生态完善、即时通讯集成便捷的核心优势,成为个人与团队搭建专属智能助手的首选方案。阿里云ECS云服务器以稳定可靠、弹性扩展、安全可控、性能强劲的特性,为OpenClaw提供7×24小时不间断运行的理想环境,彻底解决本地部署断电、断网、公网无法访问的痛点。
1020 2
|
SQL 人工智能 分布式计算
在数据浪潮中前行:我与ODPS的实践、思考与展望
在数据驱动决策的时代,企业如何高效处理海量数据成为数字化转型关键。本文结合作者实践,深入解析阿里云自研大数据平台 ODPS 的技术优势与应用场景,涵盖 MaxCompute、DataWorks、Hologres 等核心产品,分享从数据治理到实时分析的落地经验,并展望其在 AI 与向量数据时代的发展前景。
757 70
|
数据采集 监控 数据库
爬虫技术详解:从原理到实践
本文详细介绍了爬虫技术,从基本概念到实际操作,涵盖爬虫定义、工作流程及Python实现方法。通过使用`requests`和`BeautifulSoup`库,演示了如何发送请求、解析响应、提取和保存数据,适合初学者学习。强调了遵守法律法规的重要性。
5185 4
|
存储 人工智能 算法
大模型4-bit量化技术详解
本文系统阐述大语言模型的4-bit量化技术,深入解析GPTQ、AWQ等主流量化方法的原理与实现。通过详细的数学推导、代码实现和实验对比,展示4-bit量化如何将模型内存占用降低75%以上同时保持模型性能。文章涵盖量化感知训练、后训练量化、混合精度量化等关键技术,为开发者提供完整的模型压缩解决方案。
2443 7