Написано: 11.03.2023
40. Сумма комбинаций II (Combination Sum II)
Задание.
Получена коллекция кандидатов (candidates) и номер (target).
Нужно найти все уникальные комбинации в кандидатах, где номера кандидатов суммируются с target.
Каждое число в кандидатах может быть использовано только один раз в комбинации.
Примечание: Набор решений не должен содержать повторяющихся комбинаций.
Пример 1.
Входные данные: candidates = [10,1,2,7,6,1,5], target = 8
Результат: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Пример 2.
Входные данные: candidates = [2,5,2,1,2], target = 5
Результат: [ [1,2,2], [5] ]
Решение.
class Solution {
private:
vector<vector<int>> res;
void getcomb(vector <int> &nums, int i, int sum, vector <int> &cur){
int len = (int)nums.size();
if(sum == 0){
res.push_back(cur);
} else {
for(int k = i; k < len; k++) {
if(k > i && nums[k] == nums[k-1] ) continue;
if(nums[k] > sum) break;
cur.push_back(nums[k]);
getcomb(nums, k+1, sum - nums[k], cur);
cur.pop_back();
}
}
return;
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector <int> cur;
getcomb(candidates, 0, target, cur);
return res;
}
};
Пояснение.
Используется рекурсия и алгоритм с возвратом.