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 in candidates.
  • is_leaf: if remaining == 0 we have reached our target using elements in path.
  • get_edges: all candidates in candidates[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 Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What'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