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

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

Пример:

  
Input: candidates = [10,1,2,7,6,1,5], target = 8  
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

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

1⃣ Отсортировать массив candidates для возможности пропуска дубликатов.

2⃣. Запустить рекурсивную функцию backtrack(start, trackSum):
- Если trackSum == target — сохранить копию текущей комбинации
- Если trackSum > target — прекратить ветку
- На каждом шаге пропускать повторяющиеся элементы (если i > start && nums[i] == nums[i - 1])
- Не переиспользовать текущий элемент — следующий вызов с i + 1

3⃣ Использовать track для текущей комбинации и trackSum для суммы

😎 Решение:

var combinationSum2 = function(candidates, target) {
    const res = [];
    const track = [];
    let trackSum = 0;

    const backtrack = (nums, start) => {
        if (trackSum === target) {
            res.push([...track]);
            return;
        }
        if (trackSum > target) return;

        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            track.push(nums[i]);
            trackSum += nums[i];
            backtrack(nums, i + 1);
            track.pop();
            trackSum -= nums[i];
        }
    }

    candidates.sort((a, b) => a - b);
    backtrack(candidates, 0);
    return res;
};

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