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 <= 100
1 <=Ā candidates[i] <= 50
1 <= target <= 30
Solution
The logics for the template are:
start_index
: the start index of the next potential candidate incandidates
.is_leaf
: ifremaining == 0
we 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
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhat's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job 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
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