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

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

Пример:

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

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

1⃣Используем рекурсию + backtracking, начиная с индекса start_idx, чтобы избежать дубликатов.

2⃣На каждом шаге:
- добавляем candidates[i] в текущую комбинацию
- если сумма меньше target, продолжаем поиск
- если сумма равна target, сохраняем копию комбинации
- затем откатываем шаг (pop и вычитаем)

3⃣Повторное использование чисел реализуется тем, что при рекурсивном вызове мы снова передаём i, а не i + 1.

😎Решение:

var combinationSum = function(candidates, target) {
    let sols = [];

    let sum_rec = (curr_trial, curr_sum, start_idx) => {
        for (let i = start_idx; i < candidates.length; i++) {
            const c = candidates[i];
            curr_sum += c;
            curr_trial.push(c);

            if (curr_sum < target) {
                sum_rec(curr_trial, curr_sum, i);
            } else if (curr_sum === target) {
                sols.push([...curr_trial]);
            }

            curr_sum -= c;
            curr_trial.pop();
        }
    };

    sum_rec([], 0, 0);
    return sols;
};

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