Сумма комбинаций

JavaScript

class Solution {
    // Решение с использованием бэктрекинга
    combinationSum(nums, target) {
        const result = [];
        this.backtrack(nums, target, [], 0, result);
        return result;
    }
    
    backtrack(nums, target, current, start, result) {
        if (target === 0) {
            result.push([...current]);
            return;
        }
        
        for (let i = start; i < nums.length; i++) {
            if (nums[i] > target) continue;
            current.push(nums[i]);
            this.backtrack(nums, target - nums[i], current, i, result);
            current.pop();
        }
    }
    // Время: O(n^target), Память: O(target)

    // Решение с использованием динамического программирования
    combinationSumDP(nums, target) {
        const dp = Array(target + 1).fill().map(() => []);
        dp[0].push([]);
        
        for (const num of nums) {
            for (let i = num; i <= target; i++) {
                for (const comb of dp[i - num]) {
                    dp[i].push([...comb, num]);
                }
            }
        }
        return dp[target];
    }
    // Время: O(n * target * комбинации), Память: O(target * комбинации)
}

Python

class Solution:
    # Решение с использованием бэктрекинга
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        def backtrack(start: int, target: int, current: List[int]) -> None:
            if target == 0:
                result.append(current[:])
                return
            
            for i in range(start, len(nums)):
                if nums[i] > target:
                    continue
                current.append(nums[i])
                backtrack(i, target - nums[i], current)
                current.pop()
        
        result = []
        nums.sort()  # Сортировка для оптимизации
        backtrack(0, target, [])
        return result
    # Время: O(n^target), Память: O(target)

    # Решение с использованием итеративного подхода
    def combinationSumIterative(self, nums: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target + 1)]
        dp[0] = [[]]
        
        for num in nums:
            for i in range(num, target + 1):
                for comb in dp[i - num]:
                    dp[i].append(comb + [num])
        
        return dp[target]
    # Время: O(n * target * комбинации), Память: O(target * комбинации)

Java

class Solution {
    // Решение с использованием бэктрекинга
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] nums, int target, int start, 
                          List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > target) continue;
            current.add(nums[i]);
            backtrack(nums, target - nums[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
    // Время: O(n^target), Память: O(target)

    // Решение с использованием сортировки и оптимизации
    public List<List<Integer>> combinationSumOptimized(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // Сортировка для оптимизации
        backtrackOptimized(nums, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrackOptimized(int[] nums, int target, int start, 
                                  List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < nums.length && nums[i] <= target; i++) {
            current.add(nums[i]);
            backtrackOptimized(nums, target - nums[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
    // Время: O(n^target), Память: O(target)
}