Combination Sum II
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.
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] ]
Constraints:
1 <=Â candidates.length <= 1001 <=Â candidates[i] <= 501 <= target <= 30
Solution
The logics for the template are:
start_index: the start index of the next potential candidate incandidates.is_leaf: ifremaining == 0we have reached our target using elements inpath.get_edges: all candidates incandidates[start_index:].is_valid:candidate[i]is valid if it does not exceed remaining and is not a duplicate.
We will follow the same steps as in Deduplication to validate and avoid a duplicate candidate.
Implementation
1def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
2 def dfs(start_index, path, remaining):
3 if remaining == 0:
4 ans.append(path[:])
5 for i in range(start_index, len(candidates)):
6 if remaining - candidates[i] < 0: # avoid results exceeding target
7 break
8 elif i != start_index and candidates[i] == candidates[i-1]: # avoid duplicates
9 continue
10 path.append(candidates[i])
11 dfs(i+1, path, remaining - candidates[i])
12 path.pop()
13 candidates.sort()
14 ans = []
15 dfs(0, [], target)
16 return ans
Which of these pictures shows the visit order of a depth-first search?
Solution Implementation
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Patterns The Shortest Path Algorithm for Coding Interviews The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we can determine the
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.