age-935d3f20891d8cfc.js"],"default"] 17:I[4018,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:Tc1d,

Problem

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Examples

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
	[1,1,6],
	[1,2,5],
	[1,7],
	[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
	[1,2,2],
	[5]
]

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.

Follow up of Combination Sum 1

Solution

Method 1 - Backtracking

This problem is an extension of Combination Sum 1.The difference is one number in the array can only be used ONCE. Lets consider example 1 - [10,1,2,7,6,1,5], target = 8. This kind of decision tree will result in duplicates, for eg. [1,7] and [7,1] are duplicates:

combination-sum-2-wrong-sst.excalidraw

So, we should sort the input array, and then in left choose the number, and in right we dont. Once, we have used the number, we will just keep it in the left subtree.

combination-sum-2-correct-sst.excalidraw

Note, that if we have chosen the candidate, we shouldnt choose it again. So, we are using prev value, to avoid adding duplicates.

Code

[{"language":"Java","code":"public List<List<Integer>> combinationSum2(int[] candidates, int target) {\n\tList<List<Integer>> ans = new ArrayList<> ();\n\t\n\tArrays.sort(candidates);\n\t\n\thelper(candidates, target, 0, new ArrayList<Integer>(), ans);\n\treturn ans;\n}\n\npublic void helper(int[] candidates, int target, int idx, List<Integer> subAns, List<List<Integer>> ans) {\n\tif (target == 0) {\n\t\tans.add(new ArrayList<Integer> (subAns));\n\t\treturn;\n\t}\n\tif (target<0) {\n\t\treturn;\n\t}\n\n\tfor (int i = idx; i<candidates.length; i++) {\n\t\tif(i > idx && candidates[i-1] == candidates[i]){\n\t\t\tcontinue;\n\t\t}\n\t\t// each time start from different element\n\t\tsubAns.add(candidates[i]);\n\t\thelper(candidates, target - candidates[i], i+1, subAns, ans); // and use next element only\n\t\tsubAns.remove(subAns.size() - 1);\t\n\t}\n}","lang":"java"}]

8:["$","di

Related Tags