План курса / Все задачи / Алгоритмы и структуры данных

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

средне

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

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

Пример 1:

Ввод: nums = [2,3,6,7], x = 7
Вывод: [[2,2,3],[7]]
Объяснение: 2 + 2 + 3 = 7 — можно использовать 2 несколько раз. 7 уже равно x, поэтому это тоже подходит. Это единственные возможные комбинации.

Пример 2:

Ввод: nums = [1,2,2,3], x = 6
Вывод: [[2,2,2],[3,3],[3,2,1],[1,1,1,1,1,1],[1,1,1,1,2],[1,1,2,2],[1,1,1,3]]

Пример 3:

Ввод: nums = [9], x = 1
Вывод: []

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

len(nums) >= 1

class Solution
{
    public static void Bruteforce(List<int> nums, int idx, int currSum, int x, List<int> combination, List<List<int>> allCombinations)
    {
        if (currSum == x)
        {
            // Копируем список combination (создаёт новый список с теми же элементами)
            // Если сумма равна нужной, то добавляем комбинацию в результат
            allCombinations.Add(new List<int>(combination));
            return;
        }

        if (idx >= nums.Count || currSum > x)
            return;

        // Пропускаем текущее число
        Bruteforce(nums, idx + 1, currSum, x, combination, allCombinations);

        // Берём текущее число в комбинацию
        combination.Add(nums[idx]);
        Bruteforce(nums, idx, currSum + nums[idx], x, combination, allCombinations);
        combination.RemoveAt(combination.Count - 1);
    }

    public static List<List<int>> Combinations(List<int> nums, int x)
    {
        // Убираем дубликаты и сортируем массив
        // Сортируем, чтобы раньше остановиться и уменьшить число перебираемых вариантов
        nums = new HashSet<int>(nums).ToList();
        nums.Sort();

        var allCombinations = new List<List<int>>();
        Bruteforce(nums, 0, 0, x, new List<int>(), allCombinations);
        return allCombinations;
    }
}

#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

void bruteforce(const vector<int>& nums, int idx, int currSum, int x, vector<int>& combination, vector<vector<int>>& allCombinations) {
    if (currSum == x) {
        // Копируем список combination (создаём новый список с теми же элементами)
        // Если сумма равна нужной, то добавляем комбинацию в результат
        allCombinations.push_back(combination);
        return;
    }

    if (idx >= nums.size() || currSum > x)
        return;

    // Пропускаем текущее число
    bruteforce(nums, idx + 1, currSum, x, combination, allCombinations);

    // Берём текущее число в комбинацию
    combination.push_back(nums[idx]);
    bruteforce(nums, idx, currSum + nums[idx], x, combination, allCombinations);
    combination.pop_back();
}

vector<vector<int>> combinations(vector<int> nums, int x) {
    // Убираем дубликаты и сортируем массив
    // Сортируем, чтобы раньше остановиться и уменьшить число перебираемых вариантов
    unordered_set<int> uniqueSet(nums.begin(), nums.end());
    nums = vector<int>(uniqueSet.begin(), uniqueSet.end());
    sort(nums.begin(), nums.end());

    vector<vector<int>> allCombinations;
    vector<int> combination;
    bruteforce(nums, 0, 0, x, combination, allCombinations);
    return allCombinations;
}

package main

import (
    "sort"
)

func removeDuplicatesAndSort(nums []int) []int {
    // Убираем дубликаты и сортируем массив
    // Сортируем, чтобы раньше остановиться и уменьшить число перебираемых вариантов
    seen := map[int]bool{}
    result := []int{}
    for _, n := range nums {
        if !seen[n] {
            seen[n] = true
            result = append(result, n)
        }
    }
    sort.Ints(result)
    return result
}

func bruteforce(nums []int, idx int, currSum int, x int, combination []int, allCombinations *[][]int) {
    if currSum == x {
        // Копируем список combination (создаёт новый список с теми же элементами)
        // Если сумма равна нужной, то добавляем комбинацию в результат
        copyCombo := append([]int{}, combination...)
        *allCombinations = append(*allCombinations, copyCombo)
        return
    }
    if idx >= len(nums) || currSum > x {
        return
    }

    // Пропускаем текущее число
    bruteforce(nums, idx+1, currSum, x, combination, allCombinations)

    // Берём текущее число в комбинацию
    combination = append(combination, nums[idx])
    bruteforce(nums, idx, currSum+nums[idx], x, combination, allCombinations)
    combination = combination[:len(combination)-1]
}

func combinations(nums []int, x int) [][]int {
    nums = removeDuplicatesAndSort(nums)
    allCombinations := [][]int{}
    combination := []int{}
    bruteforce(nums, 0, 0, x, combination, &allCombinations)
    return allCombinations
}

import java.util.*;

public class Solution {
    public static void bruteforce(List<Integer> nums, int idx, int currSum, int x, List<Integer> combination, List<List<Integer>> allCombinations) {
        if (currSum == x) {
            // Копируем список combination (создаёт новый список с теми же элементами)
            // Если сумма равна нужной, то добавляем комбинацию в результат
            allCombinations.add(new ArrayList<>(combination));
            return;
        }

        if (idx >= nums.size() || currSum > x) return;

        // Пропускаем текущее число
        bruteforce(nums, idx + 1, currSum, x, combination, allCombinations);

        // Берём текущее число в комбинацию
        combination.add(nums.get(idx));
        bruteforce(nums, idx, currSum + nums.get(idx), x, combination, allCombinations);
        combination.remove(combination.size() - 1);
    }

    public static List<List<Integer>> combinations(List<Integer> nums, int x) {
        // Убираем дубликаты и сортируем массив
        // Сортируем, чтобы раньше остановиться и уменьшить число перебираемых вариантов
        nums = new ArrayList<>(new HashSet<>(nums));
        Collections.sort(nums);

        List<List<Integer>> allCombinations = new ArrayList<>();
        bruteforce(nums, 0, 0, x, new ArrayList<>(), allCombinations);
        return allCombinations;
    }
}

from typing import *

def bruteforce(nums: List[int], idx: int, currSum: int, x: int, сombination: List[int], all_сombinations: List[List[int]]):
    if currSum == x:
        # combination[:] — копирование списка (создаёт новый список с теми же элементами)
        # Если сумма равна нужной, то добавляем комбинацию в результат
        all_сombinations.append(сombination[:])
        return
    if idx >= len(nums) or currSum > x:
        return

    # Пропускаем текущее число
    bruteforce(nums, idx + 1, currSum, x, сombination, all_сombinations)

    # Берем текущее число в комбинацию
    сombination.append(nums[idx]) 
    bruteforce(nums, idx, currSum + nums[idx], x, сombination, all_сombinations)
    сombination.pop()

def combinations(nums: List[int], x: int) -> List[List[int]]:
    # Убираем дубликаты и сортируем массив
    # Сортируем, чтобы раньше остановиться и уменьшить число перебираемых вариантов
    nums = sorted(set(nums))
    all_сombinations = []
    bruteforce(nums, 0, 0, x, [], all_сombinations)
    return all_сombinations

export function bruteforce(nums, idx, currSum, x, combination, allCombinations) {
    if (currSum === x) {
        // Копируем список combination (создаёт новый список с теми же элементами)
        // Если сумма равна нужной, то добавляем комбинацию в результат
        allCombinations.push([...combination]);
        return;
    }

    if (idx >= nums.length || currSum > x) {
        return;
    }

    // Пропускаем текущее число
    bruteforce(nums, idx + 1, currSum, x, combination, allCombinations);

    // Берём текущее число в комбинацию
    combination.push(nums[idx]);
    bruteforce(nums, idx, currSum + nums[idx], x, combination, allCombinations);
    combination.pop();
}

export function combinations(nums, x) {
    // Убираем дубликаты и сортируем массив
    // Сортируем, чтобы раньше остановиться и уменьшить число перебираемых вариантов
    nums = Array.from(new Set(nums)).sort((a, b) => a - b);

    const allCombinations = [];
    bruteforce(nums, 0, 0, x, [], allCombinations);
    return allCombinations;
}

Оценка сложности

Время: O(n*n^(x/min(nums))), где n — размер nums, x — число, сумму которого ищем, а min(nums) минимальное значение в массиве nums.
Память: O(n*n^(x/min(nums)))

x/min(nums) — это максимальная глубина стека, при переборе всех вариантов. В каждой рекурсивной ветке мы перебираем максимум n возможных чисел, отсюда и возникает оценка O(n*n^(x/min(nums))).