LeetCode 039 Combination Sum
2024-10-18 18:05:00
题目要求:Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7
and target 7
,
A solution set is: [7]
[2, 2, 3]
代码如下:
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(candidates.begin(), candidates.end());
vector<int>::iterator pos = unique(candidates.begin(), candidates.end());
candidates.erase(pos, candidates.end()); vector<vector<int> > ans;
vector<int> record;
searchAns(ans, record, candidates, target, 0);
return ans;
} private:
void searchAns(vector<vector<int> > &ans, vector<int> &record, vector<int> &candidates, int target, int idx) { if (target == 0) {
ans.push_back(record);
return;
} if (idx == candidates.size() || candidates[idx] > target) {
return;
} for (int i = target / candidates[idx]; i >= 0; i--) {
record.push_back(candidates[idx]);
} for (int i = target / candidates[idx]; i >= 0; i--) {
record.pop_back();
searchAns(ans, record, candidates, target - i * candidates[idx], idx + 1);
}
}
};
最新文章
- 便于开发的Helper类
- Java中的一个类怎么调用另一个类中的方法
- 【Unity】Update()和FixedUpdate()
- sed学习笔记
- WCF 发布使用
- js 运算符优先级
- Android Studio 设置不自动缩进匿名内部类
- C#删除微信自定义菜单
- 【转】Java 枚举7常见种用法
- Memcached源码分析之items.c
- Android开发技巧——定制仿微信图片裁剪控件
- STM32基于固件库新建MDK工程模板(精简版)
- net-tools与iproute2
- 二、两条Linux删除数据跑路命令
- 3. Spring 核心之 IOC(控制反转) &; DI(依赖注入)
- Linux之nginx服务
- shell 生成MAC地址
- Java中单例设计模式,饿汉式和懒汉式
- <;转载>;apache 配置 http://www.blogjava.net/bukebushuo/articles/229103.html
- Flash网页小游戏开发教程