Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums toT.
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]
public class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> item = new ArrayList<Integer>(); if (candidates == null || candidates.length==0) { return res; } Arrays.sort(candidates); boolean[] visited = new boolean[candidates.length]; solve(candidates,target, 0, item ,res, visited); return res; } private void solve(int[] candidates, int target, int start, List<Integer> item, List<List<Integer>> res, boolean[] visited) { // TODO Auto-generated method stub if (target < 0) { return; } if (target == 0) { res.add(new ArrayList<>(item)); return; } for (int j = start; j < candidates.length; j++) { if (!visited[j]) { if (j > 0 && candidates[j] == candidates[j-1] && visited[j-1] == false) { continue; } item.add(candidates[j]); visited[j] = true; solve(candidates,target-candidates[j], j+1, item ,res, visited); visited[j] = false; item.remove(item.size()-1); } } } }
相关推荐
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
Combination Sum II Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump Game Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and ...
Combination Sum Medium 回溯 0040 Combination Sum II Medium 回溯 0046 Permutations Medium 回溯 0047 Permutations II Medium 递归、回溯 0051 N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 ...
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 树的遍历问题也...
combinationSum ( self , candidates , target ): def backtrack ( tmp , start , end , target ): if target == 0 : ans . append ( tmp [:]) elif target > 0 : for i in range ( start , end ): tmp . append ( ...
python实现基本算法 所有组合 所有排列 所有子序列 ... Combination Sum Hamiltonian Cycle Knight Tour Minimax Minmax N Queens N Queens Math Rat In Maze Sudoku Sum Of Subsets Word Search
39/Sum.Combination Sum 40/Sum.Combination Sum 2 46.排列(回串) 47/46.排列 2 48.旋转矩阵 49.组字谜 50.(跳过)(坏问题) 53.最大子阵列 54/59.螺旋矩阵 55.跳跃游戏 57.插入间隔 58.(跳过)(Python把戏) 59....
利用双向链表模拟动态分区分配方式。。。。
CombinationSum 组合之和 完成 LinkedList 题目 说明 状态 AddTwoNumber 两数相加 完成 SwapPairs 两两交换链表中的节点 完成 String 题目 说明 状态 LongestSubstring 最长子串 完成 LongestPalindrome 最长回文...
def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ result,temp = [],[] self.combinationSumRecu(sorted(candidates),...
II], [39 Combination Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] [] Slicing Window / Two Pointers [918 Ma
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 ...
算法 数据结构,算法,动态程序,递归和一点编码的乐趣! 介绍 ...CombinationSum:数组中组合的总和 CompareArrayBST:比较二进制搜索树 DecodeNumber:解码号码的几种方法 FindMiddleShiftedSorted
leetcode 2 和 c Leetcode_imp_C Leetcode 在 C 上的实现 大批: leetcode_0001_two_sum.c leetcode_0011_max_area.c leetcode_0015_three_sum.c ...leetcode_0039_combination_sum.c 40 leetcode_0041_first_miss
func combinationSum(candidates []int, target int) (res [][]int) {path := []int{}sort.Ints(candidates)var dfs func(int, int)dfs = func(target, index int) {if target <= 0 {if target == 0 {res = ...
a program for find combination of N Number to reach a Sum. this solve sudoku puzzle.
Sum Letter Combination of a Photo Number Palindrome Par 第一节课内容结束,题目训练. 详情 Binary Search Tree (二叉查找树) 第二次课, Binary Search Tree T(n) = O(1) + T( n/2) = O(log n) T(n) = O(1) + ...
combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which...