- 浏览: 182777 次
- 性别:
- 来自: 济南
文章分类
最新评论
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]
与Combination Sum不同的是,这里数组中的元素只能使用一次,所以我们只要在寻找的过程中开始点从当前点的下一个元素开始就可以了,其他保持不变。还要注意的一点是可能会有重复元素,产生两个一样的结果,我们只需要保存一个就可以了。代码如下:
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不同的是,这里数组中的元素只能使用一次,所以我们只要在寻找的过程中开始点从当前点的下一个元素开始就可以了,其他保持不变。还要注意的一点是可能会有重复元素,产生两个一样的结果,我们只需要保存一个就可以了。代码如下:
public class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { LinkedList<Integer> list = new LinkedList<Integer>(); LinkedList<List<Integer>> llist = new LinkedList<List<Integer>>(); if(candidates == null || candidates.length == 0) return llist; java.util.Arrays.sort(candidates); getCombination(0, target, candidates, list, llist); return llist; } public void getCombination(int start, int target, int[] candidates, LinkedList<Integer> list, LinkedList<List<Integer>> llist) { for(int i = start; i < candidates.length; i++) { if(target > candidates[i]) { list.add(candidates[i]); getCombination(i + 1, target - candidates[i], candidates, list, llist); list.removeLast(); } else if(target == candidates[i]) { list.add(candidates[i]); if(!llist.contains(list)) llist.add(new LinkedList<Integer>(list)); list.removeLast(); } else { return; } } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 264Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 266You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 381Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 372Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 497Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 560Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 474Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 661Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 468The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 427Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 571Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 576Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 423All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 894Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 928Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 669Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 841Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 780You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 703For a undirected graph with tre ...
相关推荐
java java_leetcode题解之Combination Sum II.java
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
java java_leetcode题解之Combination Sum.java
java java_leetcode题解之Combination Sum IV.java
java java_leetcode题解之Combination Sum III.java
在主函数`combinationSum2`中,我们先对输入的`candidates`进行排序,然后调用`backtrack`函数开始搜索过程。最终返回的结果集`res`包含了所有满足条件的组合。 通过以上代码,我们可以解决LeetCode第40题...
js js_leetcode题解之40-combination-sum-II.js
c语言入门 C语言_leetcode题解之40-combination-sum-ii.c
最后,`combinationSum2`是对外的公共接口,它初始化结果向量`vvi`,并调用`helper`函数开始搜索过程。 总的来说,这个手稿展示了如何使用C++实现一个基于回溯和剪枝的解决方案,来解决组合问题。通过理解这个示例...
在内容中提到的滑动窗口问题,例如“Combination Sum II”和“Sliding Window + Count Map”,涉及到在连续的数据结构中寻找满足特定条件的最长或最短子串的问题。这些技术要求编写者精通如何使用哈希表来快速追踪...
java入门 java_leetcode题解之039_Combination_Sum
Combination Sum Medium 回溯 0040 Combination Sum II Medium 回溯 0046 Permutations Medium 回溯 0047 Permutations II Medium 递归、回溯 0051 N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 ...
js js_leetcode题解之39-combination-sum.js
c语言入门 C语言_leetcode题解之39-combination-sum.c
python python_leetcode题解之216_Combination_Sum_III.py
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、...Combination Sum组合总和 Combination Sum II组合总和 II Permutations全排列 Permutations II全排列 II Maximum Suba
leetcode打不开Leetcode Note Tips Tip1: Two pointer ...Combination Sum II) Tip5: 鸽笼原理要记得,如果题目说要constant extra space,八成就是用input array + swap(#41. First Missing Positive
039:Combination Sum 040:Combination Sum II 046:Permutations 047:Permutations II 051:N-Queens 052:N-Queens II 071: Letter Combinations of a Phone Number 093:Restore IP Addresses 树的遍历问题也...
代码首先定义了一个名为`Solution`的类,其中有两个方法:`bit1Count`和`combinationSum3`。`bit1Count`方法用于计算一个无符号整数中二进制形式的1的个数,而`combinationSum3`是解决该问题的主要方法。 在`bit1...