grid47 Exploring patterns and algorithms
Nov 3, 2024
7 min read
Solution to LeetCode 40: Combination Sum II Problem
You are given a collection of distinct candidate numbers and a target number. Your task is to find all unique combinations of the candidate numbers that sum up to the target. Each number in the candidates list may only be used once in each combination. The solution should exclude duplicate combinations.
Problem
Approach
Steps
Complexity
Input: You are given an array of distinct integers 'candidates' and a target integer 'target'.
• The result must not contain duplicate combinations.
Goal: The goal is to find all possible combinations where the sum equals the target, ensuring no duplicate combinations.
Steps:
• Sort the candidates to help avoid duplicates.
• Use backtracking to explore all potential combinations, considering each candidate only once per combination.
Goal: The constraints specify that the number of candidates will not exceed 100, and all values are between 1 and 50, with the target being no larger than 30.
Steps:
• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30
Assumptions:
• The candidates array contains only distinct integers.
• Explanation: For this case, the valid combinations are [2, 2] and [5].
Approach: We will use backtracking to generate combinations of candidates that sum to the target, while avoiding duplicate solutions.
Observations:
• Since each number in candidates can only be used once, we need to ensure that we do not reuse the same element multiple times in a combination.
• Sorting the candidates will help to avoid duplicate combinations, as we can skip over numbers that are the same as the previous ones.
Steps:
• Sort the candidate list.
• Use a recursive backtracking approach to explore all combinations that sum up to the target.
• Skip over duplicate elements during recursion to avoid repeating the same combination.
Empty Inputs:
• If the candidate list is empty, return an empty list since no combinations can be formed.
Large Inputs:
• For large inputs (up to 100 candidates), the algorithm must be efficient enough to avoid excessive recursive calls.
Special Values:
• If the target is smaller than the smallest candidate, return an empty list since no combinations are possible.
Constraints:
• Ensure no duplicate combinations are included in the result.
map<vector<int>, bool> mp;
vector<vector<int>> combinationSum2(vector<int>& cand, int target) {
vector<vector<int>> ans;
vector<int> tmp;
mp.clear();
sort(cand.begin(), cand.end());
bt(ans, cand, 0, target, tmp);
return ans;
}
voidbt(vector<vector<int>>&ans, vector<int>&nums, int idx,
int sum, vector<int>&tmp) {
if(sum ==0) {
ans.push_back(tmp);
return;
}
if(sum <0|| idx == nums.size()) return;
for(int i = idx; i < nums.size(); i++) {
if(i && i > idx && nums[i] == nums[i-1]) continue;
tmp.push_back(nums[i]);
bt(ans, nums, i +1, sum - nums[i], tmp);
tmp.pop_back();
}
}
1 : Map Initialization
map<vector<int>, bool> mp;
This line initializes a map `mp` to store already visited combinations to avoid duplicates.
2 : Function Declaration
vector<vector<int>> combinationSum2(vector<int>& cand, int target) {
This line declares a function named `combinationSum2` that takes a vector of candidate numbers `cand` and a target number `target` as input and returns a vector of vectors representing all unique combinations of numbers from `cand` that add up to `target`.
3 : Vector Initialization
vector<vector<int>> ans;
This line initializes an empty 2D vector `ans` to store the resulting combinations.
4 : Vector Initialization
vector<int> tmp;
This line initializes an empty vector `tmp` to store a temporary combination during the backtracking process.
5 : Map Clear
mp.clear();
This line clears the `mp` map to ensure it's empty before starting the backtracking process.
6 : Sorting
sort(cand.begin(), cand.end());
This line sorts the `cand` vector in ascending order to optimize the backtracking process and avoid duplicate combinations.
7 : Function Call
bt(ans, cand, 0, target, tmp);
This line calls the helper function `bt` to perform the backtracking process. The `ans`, `tmp`, `0`, `target`, and `cand` are passed as arguments.
8 : Return
return ans;
This line returns the `ans` vector containing all the unique combinations.
9 : Function End
}
This line closes the `combinationSum2` function.
10 : Function Declaration
voidbt(vector<vector<int>>&ans, vector<int>&nums, int idx,
int sum, vector<int>&tmp) {
This line declares a recursive backtracking function `bt` that takes the following parameters: `ans` to store the result, `tmp` to store the current combination, `idx` to track the current index in the `nums` vector, `sum` representing the remaining target sum, and `nums` the vector of candidate numbers.
This block checks the base case: 1. If the `sum` becomes 0, it means we've reached a valid combination. 2. We check if the current combination `tmp` is already present in the `mp` map. If not, we add it to the `ans` vector and mark it as visited in the `mp` map. 3. In either case, the function returns to the previous recursive call.
12 : Pruning
if(sum <0|| idx == nums.size()) return;
This line prunes the search space by checking if the `sum` becomes negative or the index `idx` reaches the end of the `nums` vector. If so, it means the current path cannot lead to a valid combination, so the function returns early.
13 : Loop Iteration
for(int i = idx; i < nums.size(); i++) {
This line starts a `for` loop to iterate over the remaining candidate numbers, starting from the current index `idx`.
14 : Skip Duplicate Candidates
if(i && i > idx && nums[i] == nums[i-1]) continue;
This line skips duplicate candidates. If the current candidate is the same as the previous one and we're not at the beginning of the loop, we skip this iteration to avoid duplicate combinations.
15 : Include the Current Candidate
tmp.push_back(nums[i]);
This line adds the current candidate number `nums[i]` to the `tmp` combination.
16 : Recursive Call (Include)
bt(ans, nums, i +1, sum - nums[i], tmp);
This line recursively calls the `bt` function with the updated `sum` (reduced by the current candidate) and the next index `i + 1` to explore the possibility of including the current candidate in the combination.
17 : Backtrack
tmp.pop_back();
This line removes the last added candidate from the `tmp` combination to backtrack to the previous state.
Best Case: O(N^2)
Average Case: O(2^N)
Worst Case: O(2^N)
Description: The time complexity arises from generating all possible combinations using backtracking. The worst case occurs when all combinations need to be checked.
Best Case: O(1)
Worst Case: O(N)
Description: Space complexity depends on the depth of the recursion and the space used for storing the combinations.
