Jobs

Interviews

Discussions

Combination Sum II

Medium

Zomato

1 view

Topics:

ArraysRecursion

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

Try coding it in LeetCode

Combination Sum II

Medium

Zomato

1 view

Topics:

ArraysRecursion

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the candidate array, and can the target sum be negative?
Can the input array contain duplicate numbers, and if so, how should I handle them to ensure unique combinations in the output?
If no combinations sum up to the target, what should I return: an empty list, null, or throw an exception?
Is there a defined limit on the length of each individual combination? If the input array is very large, is stack overflow a concern?
Are the numbers in the combinations expected to be in non-descending order, and is the order of the combinations themselves important?

Brute Force Solution

Approach

The brute force approach for this problem is all about trying every possible combination. We'll explore all the ways to pick numbers from the given set, seeing which ones add up to our target number. It's like trying every possibility until we find the right ones.

Here's how the algorithm would work step-by-step:

Start by considering the first number: either we include it, or we don't.
If we include it, we try to find combinations of other numbers that, when added to the first number, reach the target.
If we don't include it, we try to find combinations of the remaining numbers that, on their own, reach the target.
We repeat this process for each number, branching out into new possibilities based on whether or not we include that number in our combination.
For each combination we create, we check if its sum equals the target.
If a combination adds up to the target and we haven't seen that exact combination before, we add it to our list of valid solutions.
We continue exploring all possible combinations in this manner until we have exhausted all options.

Code Implementation

def combination_sum_ii_brute_force(candidates, target):
    results = []
    unique_combinations = set()

    def find_combinations(index, current_combination, current_sum):
        if current_sum == target:
            # Convert to tuple for set uniqueness check
            sorted_combination = tuple(sorted(current_combination))
            if sorted_combination not in unique_combinations:
                results.append(current_combination[:])
                unique_combinations.add(sorted_combination)
            return
        
        if current_sum > target or index >= len(candidates):
            return

        # Explore including the current candidate
        current_combination.append(candidates[index])
        find_combinations(index + 1, current_combination, current_sum + candidates[index])
        current_combination.pop()

        # Crucial step: Exclude current candidate.
        find_combinations(index + 1, current_combination, current_sum)

    find_combinations(0, [], 0)
    return results

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible subsets of the input array. For each element, we have two choices: include it in the combination or exclude it. This branching creates a binary tree-like structure where each level corresponds to an element in the input array of size n. Therefore, in the worst case, we explore all 2^n possible combinations. Checking each combination for the target sum takes O(n) time, but this factor is dominated by the exponential growth of combinations, making the overall time complexity O(2^n * n). In the simplified version, because 2^n grows much faster, the Big O notation is O(2^n).

Space Complexity

O(N) – The space complexity is dominated by the recursion stack. In the worst case, where no numbers are skipped, the depth of the recursion tree can go up to N, where N is the number of candidates. Each recursive call creates a new stack frame, requiring memory to store local variables and the return address. Additionally, the temporary list to store the current combination of numbers could grow up to size N in the worst case. Therefore, the overall auxiliary space is O(N).

Optimal Solution

Approach

The key is to explore combinations in a structured way, avoiding redundant calculations caused by duplicate numbers. By carefully making each decision in a controlled manner, you can find all unique combinations that sum to the target efficiently. This also involves pre-processing the numbers to make the search more efficient.

Here's how the algorithm would work step-by-step:

First, sort the numbers from smallest to largest. This makes it easier to avoid duplicate combinations.
Begin building combinations one number at a time. Think of it like exploring a decision tree.
At each step, consider whether to include the current number or not. If you do include it, update the remaining sum you need to reach the target.
If you reach a point where the remaining sum is zero, you've found a valid combination. Save it.
To avoid duplicate combinations caused by identical numbers, before including a number, check if the previous number was the same and wasn't included in the last combination. If so, skip the current number to prevent redundant explorations.
When exploring a combination, if you've gone past the target value, stop that branch of exploration because it won't lead to a valid combination.
Continue this process until you've explored all possible valid combinations in a structured way.

Code Implementation

def combination_sum_two(candidates, target):
    result = []
    candidates.sort()

    def backtrack(combination, remaining_target, start_index):
        if remaining_target == 0:
            result.append(combination[:])
            return

        if remaining_target < 0:
            return

        for i in range(start_index, len(candidates)):
            # Prevent duplicate combinations
            if i > start_index and candidates[i] == candidates[i - 1]:
                continue

            current_candidate = candidates[i]

            # Explore including the current number
            combination.append(current_candidate)
            backtrack(combination, remaining_target - current_candidate, i + 1)

            # Backtrack: remove the current number to explore other possibilities
            combination.pop()

    backtrack([], target, 0)
    return result

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations of numbers to find those that sum to the target. In the worst-case scenario, where no combination sums to the target or the target is a small value compared to the numbers, the algorithm effectively generates the power set of the input array. This involves exploring each element and deciding whether or not to include it in a potential combination. Thus the time complexity grows exponentially with the size of the input array n, leading to a O(2^n) time complexity.

Space Complexity

O(N) – The algorithm uses recursion, and in the worst-case scenario, the depth of the recursion can be N, where N is the number of candidates. Each recursive call adds a new frame to the call stack. Furthermore, a temporary list is used to store the current combination; in the worst case, this list could also grow to a size of N, representing a possible combination. Therefore, the auxiliary space used by the recursion stack and the temporary list contributes O(N) space complexity.

Edge Cases

Case	How to Handle
Empty candidates array	Return an empty list since there are no numbers to form combinations.
Null candidates array	Throw an IllegalArgumentException or return an empty list, depending on desired behavior and constraints, to prevent a NullPointerException.
Target is zero	Return a list containing an empty list if the candidates contains a zero, and an empty list if not.
Candidates array contains negative numbers	The problem statement typically forbids negative numbers, so either throw an IllegalArgumentException or filter out negative values from the input array before processing.
Candidates array contains duplicate numbers that can lead to duplicate combinations	Sort the candidates array and skip over duplicate numbers during the recursive calls to avoid generating the same combination multiple times.
Target is negative	Return an empty list because with positive candidates it is impossible to reach a negative target.
Target is unreachable with the given candidates	Return an empty list after exploring all possible combinations without finding any that sum up to the target.
Candidates array contains very large numbers that could lead to integer overflow when summing	If the sum exceeds the maximum integer value, either switch to using long to store intermediate sums, or if the sum becomes greater than target, backtrack to avoid integer overflow issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the candidate array, and can the target sum be negative?
Can the input array contain duplicate numbers, and if so, how should I handle them to ensure unique combinations in the output?
If no combinations sum up to the target, what should I return: an empty list, null, or throw an exception?
Is there a defined limit on the length of each individual combination? If the input array is very large, is stack overflow a concern?
Are the numbers in the combinations expected to be in non-descending order, and is the order of the combinations themselves important?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first number: either we include it, or we don't.
If we include it, we try to find combinations of other numbers that, when added to the first number, reach the target.
If we don't include it, we try to find combinations of the remaining numbers that, on their own, reach the target.
We repeat this process for each number, branching out into new possibilities based on whether or not we include that number in our combination.
For each combination we create, we check if its sum equals the target.
If a combination adds up to the target and we haven't seen that exact combination before, we add it to our list of valid solutions.
We continue exploring all possible combinations in this manner until we have exhausted all options.

Code Implementation

def combination_sum_ii_brute_force(candidates, target):
    results = []
    unique_combinations = set()

    def find_combinations(index, current_combination, current_sum):
        if current_sum == target:
            # Convert to tuple for set uniqueness check
            sorted_combination = tuple(sorted(current_combination))
            if sorted_combination not in unique_combinations:
                results.append(current_combination[:])
                unique_combinations.add(sorted_combination)
            return
        
        if current_sum > target or index >= len(candidates):
            return

        # Explore including the current candidate
        current_combination.append(candidates[index])
        find_combinations(index + 1, current_combination, current_sum + candidates[index])
        current_combination.pop()

        # Crucial step: Exclude current candidate.
        find_combinations(index + 1, current_combination, current_sum)

    find_combinations(0, [], 0)
    return results

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort the numbers from smallest to largest. This makes it easier to avoid duplicate combinations.
Begin building combinations one number at a time. Think of it like exploring a decision tree.
At each step, consider whether to include the current number or not. If you do include it, update the remaining sum you need to reach the target.
If you reach a point where the remaining sum is zero, you've found a valid combination. Save it.
To avoid duplicate combinations caused by identical numbers, before including a number, check if the previous number was the same and wasn't included in the last combination. If so, skip the current number to prevent redundant explorations.
When exploring a combination, if you've gone past the target value, stop that branch of exploration because it won't lead to a valid combination.
Continue this process until you've explored all possible valid combinations in a structured way.

Code Implementation

def combination_sum_two(candidates, target):
    result = []
    candidates.sort()

    def backtrack(combination, remaining_target, start_index):
        if remaining_target == 0:
            result.append(combination[:])
            return

        if remaining_target < 0:
            return

        for i in range(start_index, len(candidates)):
            # Prevent duplicate combinations
            if i > start_index and candidates[i] == candidates[i - 1]:
                continue

            current_candidate = candidates[i]

            # Explore including the current number
            combination.append(current_candidate)
            backtrack(combination, remaining_target - current_candidate, i + 1)

            # Backtrack: remove the current number to explore other possibilities
            combination.pop()

    backtrack([], target, 0)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty candidates array	Return an empty list since there are no numbers to form combinations.
Null candidates array	Throw an IllegalArgumentException or return an empty list, depending on desired behavior and constraints, to prevent a NullPointerException.
Target is zero	Return a list containing an empty list if the candidates contains a zero, and an empty list if not.
Candidates array contains negative numbers	The problem statement typically forbids negative numbers, so either throw an IllegalArgumentException or filter out negative values from the input array before processing.
Candidates array contains duplicate numbers that can lead to duplicate combinations	Sort the candidates array and skip over duplicate numbers during the recursive calls to avoid generating the same combination multiple times.
Target is negative	Return an empty list because with positive candidates it is impossible to reach a negative target.
Target is unreachable with the given candidates	Return an empty list after exploring all possible combinations without finding any that sum up to the target.
Candidates array contains very large numbers that could lead to integer overflow when summing	If the sum exceeds the maximum integer value, either switch to using long to store intermediate sums, or if the sum becomes greater than target, backtrack to avoid integer overflow issues.