首页 > Python资料 博客日记
组合求和2
2024-08-14 01:00:10Python资料围观80次
题目描述:
Given a collection of candidate numbers (candidates
) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sum to target
.
Each number in candidates
may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
求解思路:
使用回溯(backtrack)算法。首先将原数组candidates按照取值从小到大排序,然后依次寻找可能求和等于目标值target的子数组。
构建一维动态数组combination存放可能成为候选的子数组,构建二维动态数组存放所有符合要求的子数组res。
回溯算法在子程序中完成,目标是依次遍历已排序的数组candidates中每个值,并判断当前值是否可以作为构成候选子数组的一份子。
(1)如果“目标值-当前求和=0”,也就是候选子数组的求和已经等于目标值,则结束当前回溯子过程,并把满足条件的候选子数组combination存入res中。
(2)依次遍历candidates数组时,当前值如果没有和前一个值重复,并且“目标值>= 当前求和+当前值”,则当前值有可能作为候选项。
从当前位置的下一个位置重新进入回溯子程序,直至找到满足条件的候选子数组,或者“目标值< 当前求和+当前值”,因为数组candidates已经从小到大排序,所以后续值也不可能满足条件了。
每个当前值在结束回溯子程序后,当前值都要从候选项子数组中弹出,也就是每个较小的值(当前求和+当前值<=目标值)都有可能在候选列表中,也有可能不在候选列表中,要兼顾两种情况。
代码:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> res;
vector<int> combination;
backtrack(res, combination, candidates, target, 0);
return res;
}
void backtrack(vector<vector<int>> &res, vector<int> &combination, vector<int> &candidates, int target, int index){
if (target ==0){
res.push_back(combination);
return;
}
for (int i = index; i<candidates.size()&& target>=candidates[i]; i++){
if (i==index || candidates[i] != candidates[i-1]) {
// not the same combination again
combination.push_back(candidates[i]);
backtrack(res, combination, candidates, target-candidates[i], i+1);
combination.pop_back();
}
}
}
标签:
相关文章
最新发布
- 光流法结合深度学习神经网络的原理及应用(完整代码都有Python opencv)
- Python 图像处理进阶:特征提取与图像分类
- 大数据可视化分析-基于python的电影数据分析及可视化系统_9532dr50
- 【Python】入门(运算、输出、数据类型)
- 【Python】第一弹---解锁编程新世界:深入理解计算机基础与Python入门指南
- 华为OD机试E卷 --第k个排列 --24年OD统一考试(Java & JS & Python & C & C++)
- Python已安装包在import时报错未找到的解决方法
- 【Python】自动化神器PyAutoGUI —告别手动操作,一键模拟鼠标键盘,玩转微信及各种软件自动化
- Pycharm连接SQL Sever(详细教程)
- Python编程练习题及解析(49题)
点击排行
- 版本匹配指南:Numpy版本和Python版本的对应关系
- 版本匹配指南:PyTorch版本、torchvision 版本和Python版本的对应关系
- Python 可视化 web 神器:streamlit、Gradio、dash、nicegui;低代码 Python Web 框架:PyWebIO
- 相关性分析——Pearson相关系数+热力图(附data和Python完整代码)
- Anaconda版本和Python版本对应关系(持续更新...)
- Python与PyTorch的版本对应
- Windows上安装 Python 环境并配置环境变量 (超详细教程)
- Python pyinstaller打包exe最完整教程