新博文地址:
[leetcode]Combination SumII
Combination Sum II
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.
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 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
Each number in C may only be used once in the combination.
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 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
具体思路跟Combination Sum 差不多,只不过不允许重复,只能从数组中拿数字,这就增加了一点难度,如果单纯的用dfs,如何避免出现[1,2,3,3,3,4,5] - 6中找到了[1,2,3][1,2,3][1,2,3][3,3][3,3],[3,3]等重复组合?
我本来尝试接触所有子集,并且从中寻找和为target的子集。这种思路很暴力,但是好在简单,但是时间复杂度已经高达O(n!),必挂无疑。不过还是可以作为参考的。
这个是TLE代码,不感兴趣就直接跳过
public List<List<Integer>> combinationSum2(int[] num, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); Arrays.sort(num); int length = num.length - 1; for(; length >= 0 && num[length] > target ;length--); if(length <= 0){ return result; } int[] newNum = Arrays.copyOf(num, length + 1); Set<List<Integer>> combination = getCombination(newNum,target); for(List<Integer> list : combination){ if(getSum(list) == target){ result.add(list); } } return result; } private int getSum(List<Integer> list){ int sum = 0; for(int tem : list){ sum += tem; } return sum; } private Set<List<Integer>> getCombination(int[] num,int target){//时间复杂度太大了 Set<List<Integer>> combination = new HashSet<List<Integer>>(); if(num.length == 1){ List<Integer> list = new ArrayList<Integer>(); list.add(num[0]); combination.add(list); return combination; } int[] preNum = Arrays.copyOf(num, num.length - 1); Set<List<Integer>> preCombination = getCombination(preNum,target); for(List<Integer> list : preCombination){ List<Integer> copy = new ArrayList<Integer>(list); if(getSum(copy) < target){ copy.add(num[num.length - 1]); combination.add(copy); } } List<Integer> singleElement = new ArrayList<Integer>(); singleElement.add(num[num.length - 1]); combination.addAll(preCombination); combination.add(singleElement); return combination; }
这里没有考虑空集,因为空集肯定不满足条件,当然别的情况下,可能需要考虑空集。
毫无疑问,该算法是个坑。
因此考虑Combination Sum 中的算法,依然DFS,并在DFS中适当的剪枝,比如上例:在1,2,3,3,3,4,4,5,5,5,6, 查找和为7的子集,当我们找到4的时候,发现1234满足条件,那么就直接退出该层递归。因为后面的要么还是1234 = 7,要么>7。然后退到了index = 2(num = 3)的这层递归,看到3的后面还是3,直接跳过,因为如果index = 3的这个3,这一层如果能找到合法序列,那么在index=2这个3的这一层,必然能找到相同的合法序列。即,前者是完全cover后者的,因此我们向后找,找到第一个不为3的数字4,既然从4开始dfs,可能比较绕,仔细想一下不难明白。
代码如下:
List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<List<Integer>> combinationSum2(int[] num, int target) { Arrays.sort(num); int length = num.length -1; for(; length >= 0 && num[length] > target ;length--); if(length < 0){ return result; } int[] newNum = Arrays.copyOf(num, length + 1); //以上只是做了一个简答的预处理,完全可以不写,对复杂度也无影响 for(int i = 0 ; i < newNum.length; i++){ dfs(new ArrayList<Integer>(),newNum,i,target); for(int j = i + 1; j < newNum.length && newNum[j] == newNum[i];j++,i++); } return result; } private void dfs(List<Integer> list,int[] num ,int index,int target){ if(index >= num.length){ return; } if(num[index] == target){ List<Integer> copy = new ArrayList<Integer>(list); copy.add(target); result.add(copy); } if(num[index] >= target){ return; } list.add(num[index]); for(int j = index + 1; j < num.length; j++){ dfs(list, num, j, target - num[index]); if(num[j] >= target - num[index]){//dont search the same combination break; } for(int k = j + 1; k < num.length && num[k] == num[j];k++,j++); } list.remove(list.size() - 1); }
相关推荐
java java_leetcode题解之Combination Sum II.java
java java_leetcode题解之Combination Sum.java
java java_leetcode题解之Combination Sum IV.java
java java_leetcode题解之Combination Sum III.java
c语言入门 C语言_leetcode题解之40-combination-sum-ii.c
js js_leetcode题解之40-combination-sum-II.js
java入门 java_leetcode题解之039_Combination_Sum
c语言入门 C语言_leetcode题解之39-combination-sum.c
js js_leetcode题解之39-combination-sum.js
python python_leetcode题解之216_Combination_Sum_III.py
239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses 589 244 Reverse Integer 591 245 Palindrome Number 593
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
在内容中提到的滑动窗口问题,例如“Combination Sum II”和“Sliding Window + Count Map”,涉及到在连续的数据结构中寻找满足特定条件的最长或最短子串的问题。这些技术要求编写者精通如何使用哈希表来快速追踪...
leetcode打不开Leetcode Note Tips Tip1: Two pointer for sorted array (#Array 1. Two Sum) Tip2: Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. Subarray Sum Equals K) Tip3: Knapsack ...
在主函数`combinationSum2`中,我们先对输入的`candidates`进行排序,然后调用`backtrack`函数开始搜索过程。最终返回的结果集`res`包含了所有满足条件的组合。 通过以上代码,我们可以解决LeetCode第40题...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
Leetcode\combination sum(39).swift Leetcode\count number of team(1395).swift Leetcode\counting bits(338).swift Leetcode \find 数组中的所有重复项(442).swift Leetcode\find peak element(162).swift ...