Q21: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]
]
Solution:
class Solution {
public:
void findCombinations(vector<int>& candidates, int target, int start, vector<int>& current, vector<vector<int>>& result) {
if (target == 0) {
result.push_back(current);
return;
}
for (int i = start; i < candidates.size() && candidates[i] <= target; ++i) {
// Skip duplicates to avoid duplicate combinations
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
current.push_back(candidates[i]);
findCombinations(candidates, target - candidates[i], i + 1, current, result);
current.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> current;
// Sort the candidates to handle duplicates
sort(candidates.begin(), candidates.end());
findCombinations(candidates, target, 0, current, result);
return result;
}
};
Explantion:
>findCombinations Function:
.Recursive function aiming to find combinations for the target sum.
.Base case: If the target becomes zero, the current combination is considered
valid and added to the result vector.
.Iterates through the candidates, avoiding duplicates to prevent redundant combinations.
.Recursive calls explore combinations with and without the current candidate.
>CombinationSum2 Function:
.Main function orchestrating the process.
.Sorts the candidate vector to handle duplicates effectively.
.Invokes the findCombinations function to discover valid combinations.
.Returns the resulting vector containing unique combinations.
>Main Function:
.Demonstrates the usage of the combinationSum2 function with a sample
set of candidates and a target sum.
.Prints the discovered combinations to the console.
>In essence, the code employs a backtracking strategy to exhaustively explore
combinations, ensuring uniqueness and avoiding duplicate sets. Sorting is
applied to streamline the handling of duplicates, ultimately producing a vector
of unique combinations.