We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Combination Sum II

Number: 40

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, LinkedIn, Bloomberg, TikTok, Microsoft, Oracle, ByteDance, Adobe, Uber, SAP, Snap

Problem Description

Given a collection of candidate numbers and a target number, the task is to find all unique combinations in the candidates where the candidate numbers sum to the target. Each candidate can only be used once in each combination. The solution must not contain duplicate combinations.

Key Insights

  • Sort the candidates first to easily skip duplicates.
  • Use backtracking to explore all possible combinations.
  • Avoid selecting the same number (at the same recursive level) to avoid duplicate combinations.
  • Terminate recursion when the running sum exceeds the target.
  • Use indices rather than reusing elements to ensure each number is used at most once.

Space and Time Complexity

Time Complexity: O(2^n * k) in the worst case, where n is the number of candidates and k is the average length of a combination. Space Complexity: O(k) for the recursion stack and current combination (not including the space occupied by the output).

Solution

The solution is based on a backtracking algorithm. First, the candidates are sorted to handle duplicates easily. Then, a recursive function is used to build combinations. At each recursion level, iterate through the candidates starting from the current index. For each candidate:

  • Skip the candidate if it is the same as the previous one (to avoid duplicates).
  • If the candidate can be added without exceeding the target, add it to the current combination.
  • Recurse with the next index (ensuring each candidate is used only once).
  • Backtrack by removing the candidate from the current combination once completed.

Data structures used include:

  • An array or list to hold the current combination.
  • A results list to store all valid combinations.
  • Sorting is leveraged to simplify duplicate elimination.

Code Solutions

# Python Solution for Combination Sum II

def combinationSum2(candidates, target):
    # Sort candidates to handle duplicates easily.
    candidates.sort()
    results = []
    
    def backtrack(start, current_combination, current_sum):
        # If the current sum equals target, add a copy of the current combination to results.
        if current_sum == target:
            results.append(list(current_combination))
            return
        # Iterate over possible candidates starting from index 'start'.
        for i in range(start, len(candidates)):
            # Skip duplicate elements.
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            new_sum = current_sum + candidates[i]
            # If the new sum exceeds target, break the loop.
            if new_sum > target:
                break
            # Include the candidate and recurse.
            current_combination.append(candidates[i])
            backtrack(i + 1, current_combination, new_sum)
            # Backtrack: remove the last element added.
            current_combination.pop()
    
    backtrack(0, [], 0)
    return results

# Example usage:
print(combinationSum2([10,1,2,7,6,1,5], 8))
← Back to All Questions