algoadvance

Leetcode 40. Combination Sum II

Problem Statement

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:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
  [1,1,6],
  [1,2,5],
  [1,7],
  [2,6]
]

Clarifying Questions

1. Are the candidate numbers always positive?
   • Yes, the problem states that the numbers are always positive integers.
2. Can the candidates contain duplicate numbers?
   • Yes, candidates can contain duplicates, but each combination reported in the output should be unique.
3. Is the order of numbers in the combination important?
   • No, the order of numbers in a combination is not important. [1,7] is the same as [7,1].
4. Can the solution set contain the same combinations in a different order?
   • No, the solution set must contain unique combinations only.

Strategy

1. Sort the Candidates: First, sort the candidate array to help easily skip duplicates.

2. Backtracking: Use a backtracking approach to explore all potential combinations.

3. Skip Duplicates: As we generate combinations, skip candidates that are the same as the previous candidates if they are at the same level of recursion to avoid duplicates.

4. Base Conditions:

   • If the target becomes zero, store the current combination.
   • If the remaining target becomes negative, stop exploring that path.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    void backtrack(std::vector<int>& candidates, int target, int start, std::vector<int>& current_combination, std::vector<std::vector<int>>& result) {
        if (target == 0) {
            result.push_back(current_combination);
            return;
        }

        for (int i = start; i < candidates.size() && candidates[i] <= target; ++i) {
            // Skip duplicates
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            
            current_combination.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current_combination, result);
            current_combination.pop_back();
        }
    }
    
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> current_combination;
        
        // Sort the candidates to handle duplicates and to make it easier to stop when the sum exceeds the target.
        std::sort(candidates.begin(), candidates.end());
        
        backtrack(candidates, target, 0, current_combination, result);
        
        return result;
    }
};

Time Complexity

• Sorting: (O(n \log n)) where (n) is the number of candidates.
• Backtracking: In the worst case, the backtracking process could explore all subsets of candidates which is (O(2^n)).
• Overall Time Complexity: The overall time complexity is (O(n \log n + 2^n)) since the expensive part is the backtracking exploration of all subsets.

This completes the problem-solving process for Combination Sum II. If there are any more questions or adjustments needed, feel free to ask!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?