5,4,2,3,2,4,9
10
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

from functools import lru_cache  # 引入lru_cache用于缓存递归结果，优化性能

def find_combinations(nums, target):
    # 使用lru_cache装饰器，缓存递归结果，None表示不限制缓存的数量
    @lru_cache(None)
    def dp(i, remaining):
        # 如果剩余目标为0，说明当前组合已经满足条件，返回1
        if remaining == 0:
            return 1
        # 如果剩余目标小于0或者已经遍历完所有元素，返回0
        if remaining < 0 or i == len(nums):
            return 0
        # 递归两种选择：选择当前元素nums[i]，或者不选择当前元素
        include = dp(i + 1, remaining - nums[i])  # 包括当前元素
        exclude = dp(i + 1, remaining)           # 不包括当前元素
        # 返回包括和不包括当前元素的总和
        return include + exclude

    # 调用dp函数，从第一个元素开始，目标和为target
    return dp(0, target)

# 读取输入
nums = list(map(int, input().split(",")))  # 输入nums列表
bag = int(input())  # 输入目标和bag

# 输出符合条件的组合数量
print(find_combinations(tuple(nums), bag))  # 将nums转换为元组传递给dp函数，因为lru_cache要求不可变类型

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28

java解法

• 解题思路
• 本题的目的是计算给定整数数组 nums 中可以组合出目标值 target 的组合数量。这是一个典型的 背包问题，其中我们可以选择或不选择每个数字，并且需要找出所有符合目标和的组合。

动态规划解法（记忆化递归）
递归建模：

我们要递归地计算：从数组的第 i 个元素开始，目标和是 remaining 时，符合条件的组合数量。
每个数字有两种选择：要么包括当前数字，要么不包括当前数字。
如果剩余目标和 remaining == 0，则返回 1，表示找到了一种组合。
如果 remaining < 0 或者遍历完所有数字，则返回 0，表示当前路径无解。
记忆化递归：

由于存在重复子问题，使用 HashMap 来缓存计算过的结果，避免重复计算。使用 (i, remaining) 作为缓存的键，i 表示当前处理的数字索引，remaining 表示剩余的目标和。
递归过程：

对于每个索引 i，我们有两种选择：
包括 nums[i]，递归处理剩余目标 remaining - nums[i]。
不包括 nums[i]，递归处理目标和 remaining。
最终返回两者的和，表示包括和不包括当前数字的所有组合。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的整数数组
        String[] input = scanner.nextLine().split(",");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i].trim());  // 将输入的字符串数组转换为整数数组
        }

        // 读取目标和
        int target = Integer.parseInt(scanner.nextLine());

        // 创建一个 Main 实例并调用 findCombinations 方法
        Main solution = new Main();
        int result = solution.findCombinations(nums, target);

        // 输出结果
        System.out.println(result);
    }

    // 存储中间结果的哈希表，用于记忆化递归
    private Map<String, Integer> memo = new HashMap<>();

    // 主方法：调用递归方法 dp 来计算组合数量
    public int findCombinations(int[] nums, int target) {
        return dp(nums, 0, target);  // 从数组的第一个元素开始，目标和为 target
    }

    // 递归方法：dp(i, remaining) 表示从索引 i 开始，目标和剩余为 remaining 时的组合数量
    private int dp(int[] nums, int i, int remaining) {
        // 如果剩余目标和为0，说明找到了一个符合要求的组合，返回1
        if (remaining == 0) {
            return 1;
        }

        // 如果剩余目标和小于0，或者遍历到数组的末尾，则说明无解，返回0
        if (remaining < 0 || i == nums.length) {
            return 0;
        }

        // 创建一个缓存键，键值为当前索引和剩余目标和
        String key = i + "," + remaining;

        // 如果当前状态已经计算过，直接返回缓存结果
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // 递归两种情况：包括当前数字 nums[i]，或者不包括当前数字
        int include = dp(nums, i + 1, remaining - nums[i]);  // 包括当前数字
        int exclude = dp(nums, i + 1, remaining);            // 不包括当前数字

        // 将当前结果存入缓存
        int result = include + exclude;
        memo.put(key, result);

        // 返回当前状态的结果
        return result;
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">