【leetcode刷题笔记】Combination Sum
2024-08-29 23:28:26
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]
题解:类似八皇后问题。每次把candidates[i]加入到numbers列表中,然后递归的搜索target-candidates[i]的组成方法。
要注意的一点是,将candidates[i]加入到numbers列表后,i前面的元素就不能再往numbers里面加了,只能再加入i本身或者i后面的元素。所以在递归函数中要有一个参数start,表明只有start本身或者以后的元素可以加入numbers中。每当递归函数参数target等于0的时候,说明找到了一组答案在numbers中,把numbers加入到answer里面就可以了。
代码如下:
public class Solution {
private void combiDfs(int[] candidates,int target,List<List<Integer>> answer,List<Integer> numbers,int start){
if(target == 0){
answer.add(new ArrayList<Integer>(numbers));
return;
}
for(int i = start;i < candidates.length;i++){
if(candidates[i] > target)
break;
numbers.add(candidates[i]);
combiDfs(candidates, target-candidates[i], answer, numbers,i);
numbers.remove(numbers.size()-1);
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> answer = new ArrayList<List<Integer>>();
List<Integer> numbers = new ArrayList<Integer>();
Arrays.sort(candidates);
combiDfs(candidates, target, answer, numbers,0); return answer; }
}
最新文章
- iOS UIButton 设置图片平铺
- bootstrap 20161012
- Missing (Mono Script), Missing Prefab
- Cantor的数表
- TCP与UDP协议
- html状态码与缓存学习
- Nexus中自定义私服,每个项目都用独立的工厂,仓库
- 【jmter】逻辑控制器(Logic Controller)
- iTween基础之Fade(淡入淡出)
- Bootstrap_表单_按钮
- 【每日一摩斯】-Troubleshooting: High CPU Utilization (164768.1) - 系列5
- Linux Kernel系列 - 黄牛X内核代码凝视
- js模拟jq获取id
- POI颜色设置
- C程序结构
- instrument(2)
- Django+Vue打造购物网站(一)
- Codeforces 233 D - Table
- 全栈性能测试修炼宝典--Jmeter实战(三)
- 【环境变量】Linux 下三种方式设置环境变量与获取环境变量
热门文章
- 事务(Transaction)概念和特性
- ubuntu下USB连接Android手机
- Asp.net MVC 插件式应用框架
- CentOS LVS安装配置
- Java 入门课程视频实战-0基础 上线了,猜拳游戏,ATM实战,欢迎围观
- MapReduce小文件处理之CombineFileInputFormat实现
- 什么是CouchDB?
- iOS 提交应用到appStore报错ITMS-90xxx
- maven 依赖文件 pom.xml 编译 mvn compile 运行 不用mvn exec:java -Dexec.mainClass=";hello.HelloWorld"; 打成jar包 mvn package mvn install http://blog.csdn.net/yaya1943/article/details/48464371
- 常用PhpStorm 快捷键