Combination Sum II

Leetcode Link

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

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    def dfs(start_index, path, remaining):
        if remaining == 0:
            ans.append(path[:])
        for i in range(start_index, len(candidates)):
            if remaining - candidates[i] < 0:   # avoid results exceeding target
                break
            elif i != start_index and candidates[i] == candidates[i-1]: # avoid duplicates
                continue
            path.append(candidates[i])
            dfs(i+1, path, remaining - candidates[i])
            path.pop()
    candidates.sort()
    ans = []
    dfs(0, [], target)
    return ans

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

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
12

1public 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}
16

1function 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}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know

Combination Sum II

Solution

Implementation

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Recommended Readings