Задача: 39. Combination Sum
Сложность: medium

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

Пример:

Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]

👨‍💻 Алгоритм:

1⃣Используем рекурсивный бэктрекинг: если остаток суммы remain == 0 — комбинация найдена, добавляем в результат.

2⃣Если remain < 0 — выходим из текущей ветки (комбинация невалидна).

3⃣Для каждой позиции i от start до конца candidates, пробуем включить элемент в комбинацию, вызываем рекурсию с уменьшенным remain, и откатываемся (pop_back) после вызова.

😎 Решение:

class Solution {
public:
    void backtrack(int remain, vector<int>& comb, int start,
                   const vector<int>& candidates,
                   vector<vector<int>>& results) {
        if (remain == 0) {
            results.push_back(comb);
            return;
        } else if (remain < 0) {
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            comb.push_back(candidates[i]);
            backtrack(remain - candidates[i], comb, i, candidates, results);
            comb.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> comb;

        backtrack(target, comb, 0, candidates, results);
        return results;
    }
};

Ставь 👍 и забирай 📚 Базу знаний