151 DSA Problem journey

151 DSA Problem journey

Combination II

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.

Did you find this article valuable?

Support GAURAV YADAV by becoming a sponsor. Any amount is appreciated!