377. Combination Sum IV

using System.Collections.Generic;
public class Solution {
    private Dictionary<int, int> memo;
    public int CombinationSum4(int[] nums, int target) {
        memo = new Dictionary<int, int>();
        return Combs(nums, target);
    }
    private int Combs(int[] nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.ContainsKey(remain))
            return memo[remain];
        int result = 0;
        foreach (int num in nums) {
            if (remain - num >= 0)
                result += Combs(nums, remain - num);
        }
        memo[remain] = result;
        return result;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<int, int> memo;
    public int CombinationSum4(vector<int>& nums, int target) {
        memo = new unordered_map<int, int>();
        return Combs(nums, target);
    }
    private int Combs(vector<int>& nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.count(remain))
            return memo[remain];
        int result = 0;
        foreach (int num in nums) {
            if (remain - num >= 0)
                result += Combs(nums, remain - num);
        }
        memo[remain] = result;
        return result;
    }
}

class Solution {
    private HashMap<Integer, Integer> memo;

    public int combinationSum4(int[] nums, int target) {
        memo = new HashMap<>();
        return combs(nums, target);
    }

    private int combs(int[] nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.containsKey(remain))
            return memo.get(remain);

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
        }
        memo.put(remain, result);
        return result;
    }
}

class Solution {
    constructor() {
        this.memo = new Map();
    }

    combinationSum4(nums, target) {
        return this.combs(nums, target);
    }

    combs(nums, remain) {
        if (remain === 0) {
            return 1;
        }
        if (this.memo.has(remain)) {
            return this.memo.get(remain);
        }

        let result = 0;
        for (const num of nums) {
            if (remain - num >= 0) {
                result += this.combs(nums, remain - num);
            }
        }
        this.memo.set(remain, result);
        return result;
    }
}

class Solution:
    def __init__(self):
        self.memo = {}

    def combinationSum4(self, nums: List[int], target: int) -> int:
        return self.combs(nums, target)

    def combs(self, nums: List[int], remain: int) -> int:
        if remain == 0:
            return 1
        if remain in self.memo:
            return self.memo[remain]

        result = 0
        for num in nums:
            if remain - num >= 0:
                result += self.combs(nums, remain - num)
        
        self.memo[remain] = result
        return result

package main

func combinationSum4(nums []int, target int) int {
    memo := make(map[int]int)
    return combs(nums, target, memo)
}

func combs(nums []int, remain int, memo map[int]int) int {
    if remain == 0 {
        return 1
    }
    if val, found := memo[remain]; found {
        return val
    }

    result := 0
    for _, num := range nums {
        if remain - num >= 0 {
            result += combs(nums, remain - num, memo)
        }
    }
    memo[remain] = result
    return result
}

Algorithm

В этом подходе мы начнем со стратегии сверху вниз, которая, пожалуй, более интуитивна. Как следует из названия, стратегия сверху вниз начинается с исходных данных, и затем мы рекурсивно уменьшаем Inputные данные до меньшего масштаба, пока не достигнем уровней, которые больше невозможно разбить.

Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию.

Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая returns количество комбинаций, где каждая комбинация в сумме дает значение remain.

😎