Combination Sum I I Algorithm
The Combination Sum II Algorithm is a backtracking algorithm used to find all unique combinations of a given set of numbers that add up to a specific target number. This algorithm is an extension of the Combination Sum Algorithm, where the primary difference is that in Combination Sum II, each number in the given set can be used only once, whereas in Combination Sum, each number can be used an unlimited number of times. The algorithm is especially useful for solving problems involving subsets or collections of numbers that must meet a specific sum criterion.
In the Combination Sum II Algorithm, we recursively explore all possible combinations of the given set of numbers to find the subsets that meet the target sum. We start with an empty combination and then extend it by adding one number at a time from the given set while ensuring that the current sum does not exceed the target sum. If the current sum becomes equal to the target sum, we add the combination to our result set. To avoid duplicate combinations, we keep track of the indices of the numbers used in the combination and ensure that we are only considering numbers with a greater index than the last used number. Backtracking is employed when the current sum exceeds the target sum or when we have used all available numbers in the set. By exploring all possible combinations in this manner, the algorithm generates a collection of unique combinations that satisfy the target sum requirement.
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
combination_set.clear();
sort(candidates.begin(), candidates.end());
vector<int> nums;
DFS(nums, target, candidates, 0);
return move(combination_set);
}
void DFS(vector<int>& nums, int target, vector<int>& candidates, int position) {
if (target < 0) return;
if (target == 0) {
if (find(combination_set.begin(), combination_set.end(), nums) == combination_set.end())
combination_set.push_back(nums);
return;
}
if (position >= candidates.size())
return;
DFS(nums, target, candidates, position + 1);
int value = candidates[position];
if (value <= target) {
nums.push_back(value);
DFS(nums, target - value, candidates, position + 1);
nums.pop_back();
}
}
private:
vector<vector<int>> combination_set;
};
