39. Combination Sum

Задача

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

Примеры

Пример 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Пояснение

2 + 2 + 3 = 7 (2 можно использовать несколько раз) и 7 = 7. Это единственные две комбинации.

Пример 2

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

Пример 3

Input: candidates = [2], target = 1
Output: []

Решение

Решение

/**
 * Combination Sum - поиск всех уникальных комбинаций чисел, дающих target
 * 
 * ВРЕМЕННАЯ СЛОЖНОСТЬ: O(N^(T/M))
 * где N = длина candidates
 *     T = target
 *     M = минимальное значение в candidates
 * 
 * Объяснение:
 * - В худшем случае дерево рекурсии имеет глубину T/M (если используем минимальное число)
 * - На каждом уровне до N ветвлений
 * - Итого N^(T/M) узлов в дереве
 * 
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: O(T/M)
 * - Глубина рекурсии = максимальная длина комбинации = T/M
 * - Стек вызовов занимает O(T/M)
 * - Массив current тоже O(T/M)
 * - Не считаем result, так как это выходные данные
 * 
 * ОПТИМИЗАЦИИ:
 * 1. Сортировка candidates - позволяет использовать break при превышении
 * 2. Break вместо продолжения цикла - отсекает заведомо большие числа
 * 3. Проверка sum > target - ранний выход из бесперспективных веток
 */
function combinationSum(candidates, target) {
    const result = [];
 
    // Сортируем для возможности early break
    candidates.sort((a, b) => a - b);
 
    function backtrack(start, currentCombination, currentSum) {
        // Базовый случай: нашли нужную сумму
        if (currentSum === target) {
            result.push([...currentCombination]); // Копируем массив
            return;
        }
 
        // Базовый случай: превысили target, дальше нет смысла
        if (currentSum > target) {
            return;
        }
 
        // Перебираем кандидатов начиная с индекса start
        for (let i = start; i < candidates.length; i++) {
            // КЛЮЧЕВАЯ ОПТИМИЗАЦИЯ: если текущее число уже слишком большое,
            // то все следующие (они отсортированы) тоже будут большими
            if (currentSum + candidates[i] > target) {
                break; // Прерываем весь цикл, а не только текущую итерацию
            }
 
            // Добавляем текущий кандидат в комбинацию
            currentCombination.push(candidates[i]);
 
            // ВАЖНО: передаем i (не i+1), чтобы разрешить повторное использование
            // того же числа на следующем уровне рекурсии
            backtrack(
                i, // start - можем использовать это число снова
                currentCombination, // текущая комбинация (модифицируется)
                currentSum + candidates[i] // новая сумма
            );
 
            // Бэктрекинг: откатываем последнее добавление
            // для проверки других вариантов
            currentCombination.pop();
        }
    }
 
    // Запускаем рекурсию с начальными значениями
    backtrack(0, [], 0);
    return result;
}
 
// Примеры использования:
console.log(combinationSum([2, 3, 6, 7], 7)); // [[2,2,3], [7]]
console.log(combinationSum([2, 3, 5], 8)); // [[2,2,2,2], [2,3,3], [3,5]]
console.log(combinationSum([2], 1)); // []