Сумма комбинаций: разбор задачи

Почему эта задача важна?

Задача "Сумма комбинаций" позволяет оценить:

• 🧠 Умение работать с рекурсией и бэктрекингом
• ⚡ Навыки генерации комбинаторных решений
• 🎯 Понимание принципов динамического программирования
• 🔍 Способность эффективно обрабатывать повторяющиеся элементы и комбинации

Постановка задачи

Формулировка:

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

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

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

Примеры:

// Первый пример ✅
Input: 
nums = [2, 5, 6, 9]
target = 9

Output: [[2, 2, 5], [9]]

Объяснение:
2 + 2 + 5 = 9 (используем 2 дважды и 5 один раз)
9 = 9 (используем 9 один раз)

// Второй пример ✅
Input:
nums = [3, 4, 5]
target = 16

Output: [[3, 3, 3, 3, 4], [3, 3, 5, 5], [3, 4, 4, 5], [4, 4, 4, 4]]

// Третий пример ✅
Input:
nums = [2, 3, 5]
target = 8

Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Ограничения:

• 1 <= nums.length <= 30
• 1 <= nums[i] <= 200
• Все элементы nums различны
• 1 <= target <= 500

Подходы к решению

Решение 1: Рекурсия с бэктрекингом 🔍

function combinationSum(nums, target) {
  const result = [];
  
  // Сортируем массив для оптимизации (необязательно, но полезно)
  nums.sort((a, b) => a - b);
  
  // Вспомогательная функция для рекурсивного поиска
  function backtrack(start, target, path) {
    // Базовый случай: если цель достигнута
    if (target === 0) {
      result.push([...path]);
      return;
    }
    
    // Перебираем все возможные числа, начиная с индекса start
    for (let i = start; i < nums.length; i++) {
      // Если текущее число больше оставшейся цели, прерываем цикл
      // (оптимизация работает благодаря предварительной сортировке)
      if (nums[i] > target) break;
      
      // Добавляем текущее число в путь
      path.push(nums[i]);
      
      // Рекурсивно ищем комбинации с текущим числом
      // Начинаем с того же индекса i, так как можно использовать число многократно
      backtrack(i, target - nums[i], path);
      
      // Убираем текущее число из пути (бэктрекинг)
      path.pop();
    }
  }
  
  backtrack(0, target, []);
  
  return result;
}

Анализ решения:

✅ Находит все уникальные комбинации

✅ Эффективно обрабатывает повторное использование элементов

✅ Избегает дублирования комбинаций

❌ Может быть неэффективен для больших значений target

❌ Временная сложность экспоненциальная в худшем случае

Решение 2: Динамическое программирование 🚀

function combinationSum(nums, target) {
  // Создаем массив для хранения всех комбинаций с суммой i
  const dp = Array(target + 1).fill().map(() => []);
  
  // Базовый случай: пустая комбинация для суммы 0
  dp[0] = [[]];
  
  // Для каждого числа в массиве
  for (const num of nums) {
    // Для каждой возможной суммы от num до target
    for (let sum = num; sum <= target; sum++) {
      // Для каждой комбинации, которая дает сумму (sum - num)
      for (const combo of dp[sum - num]) {
        // Создаем новую комбинацию, добавляя текущее число
        dp[sum].push([...combo, num]);
      }
    }
  }
  
  return dp[target];
}

Характеристики:

✅ Более систематический подход

✅ Избегает избыточных вычислений

❌ Требует значительного объема памяти

❌ Может генерировать дубликаты, требующие дополнительной обработки

Решение 3: Оптимизированная рекурсия с мемоизацией 🔧

function combinationSum(nums, target) {
  // Сортируем массив для оптимизации
  nums.sort((a, b) => a - b);
  
  // Кэш для хранения уже вычисленных результатов
  const memo = new Map();
  
  function findCombinations(start, target) {
    // Проверяем, есть ли результат в кэше
    const key = `${start}-${target}`;
    if (memo.has(key)) {
      return memo.get(key);
    }
    
    // Результаты для текущего состояния
    const result = [];
    
    // Базовый случай: если цель равна 0
    if (target === 0) {
      result.push([]);
      return result;
    }
    
    // Перебираем все возможные числа, начиная с индекса start
    for (let i = start; i < nums.length; i++) {
      // Пропускаем, если число больше цели
      if (nums[i] > target) break;
      
      // Получаем все комбинации для оставшейся суммы
      const subCombinations = findCombinations(i, target - nums[i]);
      
      // Добавляем текущее число к каждой подкомбинации
      for (const subCombo of subCombinations) {
        result.push([nums[i], ...subCombo]);
      }
    }
    
    // Сохраняем результат в кэше
    memo.set(key, result);
    
    return result;
  }
  
  return findCombinations(0, target);
}

Преимущества и недостатки:

✅ Сочетает преимущества рекурсии и динамического программирования

✅ Избегает повторных вычислений с помощью мемоизации

✅ Более эффективен по памяти, чем чистое ДП

❌ Все еще имеет экспоненциальную сложность в худшем случае

Решение 4: Поиск в глубину с итерационной оптимизацией 📊

function combinationSum(nums, target) {
  const result = [];
  
  // Сортируем массив для оптимизации
  nums.sort((a, b) => a - b);
  
  // Структура для DFS: [начальный индекс, текущая цель, текущий путь]
  const stack = [[0, target, []]];
  
  while (stack.length > 0) {
    const [start, currentTarget, path] = stack.pop();
    
    // Если текущая цель достигнута
    if (currentTarget === 0) {
      result.push([...path]);
      continue;
    }
    
    // Перебираем все возможные числа, начиная с индекса start
    for (let i = start; i < nums.length; i++) {
      // Если текущее число больше оставшейся цели, прерываем цикл
      if (nums[i] > currentTarget) break;
      
      // Создаем новый путь, добавляя текущее число
      const newPath = [...path, nums[i]];
      
      // Добавляем в стек новое состояние
      stack.push([i, currentTarget - nums[i], newPath]);
    }
  }
  
  return result;
}

Особенности:

✅ Избегает ограничений стека вызовов, присущих рекурсии

✅ Может быть более эффективным для очень глубоких поисков

❌ Менее интуитивно понятен, чем рекурсивный подход

❌ Неоптимален по памяти из-за копирования путей

Сравнение временной и пространственной сложности

где:

• N = количество элементов в массиве
• T = целевая сумма
• M = минимальное значение в массиве
• K = среднее количество комбинаций для каждой суммы

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Рекурсия с бэктрекингом - наиболее интуитивный и эффективный подход
   • 📝 Динамическое программирование может быть более эффективным для определенных входных данных
   • 🧮 Предварительная сортировка массива позволяет оптимизировать поиск

2. Важные моменты:

   • 📝 Правильная обработка повторного использования элементов
   • 🔄 Избегание дублирования комбинаций
   • 📊 Эффективное отсечение невозможных путей

Распространённые ошибки

1. 🤦‍♂️ Неправильная обработка повторяющихся комбинаций
2. 😅 Некорректное управление индексами при рекурсии
3. 🐛 Избыточное копирование данных при формировании результата
4. 😕 Неэффективное использование памяти в динамическом программировании

Визуализация алгоритма рекурсии с бэктрекингом

Рассмотрим пример nums = [2, 3, 5] и target = 8:

1. Начинаем с пустого пути [] и target = 8
   
2. Выбираем число 2:
   Path: [2], remaining target: 6
   
   2.1. Выбираем 2 снова:
       Path: [2, 2], remaining target: 4
      
       2.1.1. Выбираем 2 снова:
           Path: [2, 2, 2], remaining target: 2
          
           2.1.1.1. Выбираем 2 снова:
               Path: [2, 2, 2, 2], remaining target: 0
               Нашли комбинацию [2, 2, 2, 2], добавляем в результат
               Возвращаемся (backtrack)
          
           2.1.1.2. Выбираем 3:
               Path: [2, 2, 2, 3], remaining target: -1
               Сумма превышает target, возвращаемся
          
           2.1.1.3. Выбираем 5:
               Path: [2, 2, 2, 5], remaining target: -3
               Сумма превышает target, возвращаемся
      
       2.1.2. Выбираем 3:
           Path: [2, 2, 3], remaining target: 1
          
           2.1.2.1. Не можем выбрать ни одно число, так как все > 1
               Возвращаемся
      
       2.1.3. Выбираем 5:
           Path: [2, 2, 5], remaining target: -1
           Сумма превышает target, возвращаемся
   
   2.2. Выбираем 3:
       Path: [2, 3], remaining target: 3
      
       2.2.1. Выбираем 2:
           Path: [2, 3, 2], remaining target: 1
           Не можем выбрать ни одно число, так как все > 1
           Возвращаемся
      
       2.2.2. Выбираем 3:
           Path: [2, 3, 3], remaining target: 0
           Нашли комбинацию [2, 3, 3], добавляем в результат
           Возвращаемся
      
       2.2.3. Выбираем 5:
           Path: [2, 3, 5], remaining target: -2
           Сумма превышает target, возвращаемся
   
   2.3. Выбираем 5:
       Path: [2, 5], remaining target: 1
       Не можем выбрать ни одно число, так как все > 1
       Возвращаемся

3. Выбираем число 3:
   Path: [3], remaining target: 5
   
   3.1. Выбираем 3:
       Path: [3, 3], remaining target: 2
      
       3.1.1. Выбираем 2:
           Path: [3, 3, 2], remaining target: 0
           Нашли комбинацию [3, 3, 2], но она эквивалентна [2, 3, 3]
           которую мы уже добавили, поэтому не дублируем
           Возвращаемся
      
       3.1.2. Выбираем 3:
           Path: [3, 3, 3], remaining target: -1
           Сумма превышает target, возвращаемся
   
   3.2. Выбираем 5:
       Path: [3, 5], remaining target: 0
       Нашли комбинацию [3, 5], добавляем в результат
       Возвращаемся

4. Выбираем число 5:
   Path: [5], remaining target: 3
   
   4.1. Выбираем 2:
       Path: [5, 2], remaining target: 1
       Не можем выбрать ни одно число, так как все > 1
       Возвращаемся
   
   4.2. Выбираем 3:
       Path: [5, 3], remaining target: 0
       Нашли комбинацию [5, 3], но она эквивалентна [3, 5]
       которую мы уже добавили, поэтому не дублируем
       Возвращаемся

Итоговый результат: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Оптимизации

Предварительная проверка особых случаев

function combinationSum(nums, target) {
  // Обработка пустого массива
  if (nums.length === 0) return [];
  
  // Если target меньше минимального элемента, решения нет
  const minNum = Math.min(...nums);
  if (target < minNum) return [];
  
  // Если target равен минимальному элементу, есть только одно решение
  if (target === minNum) return [[minNum]];
  
  // Основной алгоритм
  const result = [];
  nums.sort((a, b) => a - b);
  
  function backtrack(start, target, path) {
    if (target === 0) {
      result.push([...path]);
      return;
    }
    
    for (let i = start; i < nums.length; i++) {
      if (nums[i] > target) break;
      
      path.push(nums[i]);
      backtrack(i, target - nums[i], path);
      path.pop();
    }
  }
  
  backtrack(0, target, []);
  return result;
}

Использование битовых масок для оптимизации памяти

function combinationSum(nums, target) {
  // Для небольших массивов можно использовать битовые маски
  // для эффективного представления комбинаций
  if (nums.length <= 20) {
    const result = [];
    const uniqueCombos = new Set();
    
    function generateBitMask(combo) {
      let mask = 0;
      for (const num of combo) {
        const index = nums.indexOf(num);
        mask |= (1 << index);
      }
      return mask;
    }
    
    function backtrack(start, target, path) {
      if (target === 0) {
        // Сортируем комбинацию для канонизации
        const sortedPath = [...path].sort((a, b) => a - b);
        const key = sortedPath.join(',');
        
        if (!uniqueCombos.has(key)) {
          uniqueCombos.add(key);
          result.push([...path]);
        }
        return;
      }
      
      for (let i = start; i < nums.length; i++) {
        if (nums[i] > target) continue;
        
        path.push(nums[i]);
        backtrack(i, target - nums[i], path);
        path.pop();
      }
    }
    
    backtrack(0, target, []);
    return result;
  }
  
  // Для больших массивов используем обычный алгоритм
  // ...
}

Заключение

При решении задачи "Сумма комбинаций" важно помнить:

• 🤹‍♂️ Рекурсивный подход с бэктрекингом является наиболее интуитивным и эффективным
• 📊 Предварительная сортировка массива позволяет рано отсечь невозможные пути
• 🧠 Понимание того, что каждый элемент можно использовать неограниченное количество раз, является ключевым для корректной реализации
• 🔄 Важно избегать дублирования комбинаций, но при заданных условиях (уникальные элементы и неограниченное использование) это проще, чем в общем случае

Эта задача демонстрирует мощь рекурсивных алгоритмов и бэктрекинга для решения комбинаторных задач. Она также показывает, как можно эффективно генерировать все возможные комбинации, удовлетворяющие определенным условиям, что является важным навыком в алгоритмическом программировании. 🌟