Combination Sum Two
2024-09-28 14:04:15
Description:
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
] Thoughts:
这个问题和前一个问题Combination Sum很像，区别在于它允许给定的nums中有重复数字，但是不允许对nums中的数字进行重复使用.同时还不能够出现重复的解
解决不允许对nums中的数字进行重复使用，我们只需要将下一次回溯的开始点设置为当前回溯点的下一个点即可。不能出现重复解，这个问题我们可以通过在添加解的时候判断当前的解是否已经在已有的解中来解决（另外一种解决方式是
通过添加限制条件来减少当前解的搜索空间。因为我们不允许出现重复解，但是nums中又有重复数字，因此我们只需要保证搜索路径跳过重复的数字即可。） 以下是java解法一：
package middle; import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class CombinationSum { public List<List<Integer>> combinationSum(int[] candidates, int target){
List<List<Integer>> list = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
backtrack(list, new ArrayList(),candidates, target, 0);
/* System.out.println(list);*/
return list;
} private void backtrack(List<List<Integer>> list, ArrayList arrayList,
int[] candidates, int target, int start) {
// TODO Auto-generated method stub
if(target < 0){
return;
}else if(target == 0){
//we should new an ArrayList, because the arrayList will change later,
//if we do not copy it's value, list will add []
list.add(new ArrayList<Integer>(arrayList));
}else{
for(int i = start;i<candidates.length;i++){
arrayList.add(candidates[i]);
backtrack(list, arrayList, candidates, target-candidates[i], i);
arrayList.remove(arrayList.size() - 1);
}
}
} public static void main(String[] args){
CombinationSum sum = new CombinationSum();
int[] candidates = new int[]{2, 3,5 ,7};
sum.combinationSum(candidates, 7);
}
}
这个解法采用的是通过在添加解的时候判断当前的解是否已经在已有的解中来解决重复问题
以下是java解法二：
package middle; import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class CombinationSumTwo { public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
backTrack2(list, new ArrayList(), candidates, target, 0);
return list;
} private void backTrack(List<List<Integer>> list, ArrayList arrayList,
int[] candidates, int target, int start) {
// TODO Auto-generated method stub if(target < 0){
return;
}else if (target == 0){
if(list.contains(arrayList) == false){
list.add(new ArrayList(arrayList));
}
}else{
for(int i = start; i < candidates.length;i++){
arrayList.add(candidates[i]);
backTrack(list, arrayList, candidates, target-candidates[i], i+1);
arrayList.remove(arrayList.size() - 1);
}
}
} private void backTrack2(List<List<Integer>> list, ArrayList arrayList, int[] candidates, int target, int start){
if(target < 0){
return;
}else if(target == 0){
//we should new an ArrayList, because the arrayList will change later,
//if we do not copy it's value, list will add []
list.add(new ArrayList<Integer>(arrayList));
}else{
for(int i = start;i<candidates.length;i++){
if(i > start && candidates[i] == candidates[i - 1]) continue;
arrayList.add(candidates[i]);
backTrack2(list, arrayList, candidates, target-candidates[i], i+1);
arrayList.remove(arrayList.size() - 1);
}
}
} public static void main(String[] args){
CombinationSumTwo c = new CombinationSumTwo();
int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
List<List<Integer>> l = c.combinationSum2(candidates, 8);
System.out.println(l);
} }
这个解法采用了减少搜索空间的方式来去除重复的解。
最新文章
- Transaction (Process ID xxx) was deadlocked on lock
- 十五天精通WCF——第十三天 用WCF来玩Rest
- Timer和DPC
- codeforces589J 简单dfs，队列
- PHP 递归的密码
- hdu2093
- 关于KeyEvent.Callback
- ZOJ 1654 二分匹配基础题
- linux-mkdir
- i春秋----Misc
- Java基础——多线程(持续更新中)
- 2017-10-29—英语发音的一些技巧总结
- Kafka如何彻底删除topic及数据
- File Explore 中data权限修改，实体机
- Github恶搞之自定义你的contribution图表
- Oracle数据库冷备份与热备份操作梳理
- UML 类图 说明
- drop redo logfile current报错
- xamarin其实也是一个鸡肋
- yii/helper/Html