39. Сумма комбинаций (Combination Sum)

Задание.

Получен массив различных (distinct) целых чисел candidates и целочисленное значение target

Нужно вернуть список всех уникальных комбинаций кандидатов, где выбранные числа суммируются с target. Можно возвращать комбинации в любом порядке.

Одно и то же число может быть выбрано из кандидатов неограниченное количество раз. Две комбинации уникальны, если частота хотя бы одного из выбранных чисел отличается.

Тестовые примеры генерируются таким образом, что количество уникальных комбинаций, которые в сумме приводят к цели, составляет менее 150 комбинаций для заданных входных данных.

Пример 1.

Входные данные: candidates = [2,3,6,7], target = 7

Результат: [[2,2,3],[7]]

Пояснение: 2 и 3 являются кандидатами, и 2 + 2 + 3 = 7. Обратите внимание, что 2 можно использовать несколько раз. 7 – это кандидат, и 7 = 7. Это единственные две комбинации.

Пример 2.

Входные данные: candidates = [2,3,5], target = 8

Результат: [[2,2,2,2],[2,3,3],[3,5]]

Пример 3.

Входные данные: candidates = [2], target = 1

Результат: []

Решение.

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 if(sum > 0 && i < len) {
            for(int k = i ; k < len; k++){
                cur.push_back(nums[k]);
                getcomb(nums, k, sum - nums[k], cur);
                cur.pop_back();
            }
        }
        return ;
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // sort the array in ascending order
        vector<int>cur;
        getcomb(candidates, 0, target, cur);
        return res;
    }
};

Пояснение.

Используется рекурсия и алгоритм с возвратом.