题目

小明有 n 个可选运动，每个运动有对应卡路里，想选出其中 K 个运动且卡路里和为 t。k，t，n 都是给定的。求出可行解数量

输入描述

第一行输入 n t k

第二行输入每个运动的卡路里，按照空格进行分割。

备注

0<n<10，t>0，0<k<=n

每个运动量的卡路里>0

输出描述

求出可行解数量

示例1

输入

4 3 2

1 1 2 3

输出

2

说明

可行解为 2，选取 {0,2}, {1,2} 两种方式。

解题思路

本题模式

从 n 个数中，选出 k 个不同元素，使其和为 t，求方案数。

从 n 个元素中选 k 个，使得满足某种约束，问方案数。——组合型 DFS / 回溯问题

建模

1. 状态怎么定义？

在 DFS 中，我们关心三个核心状态：

index   当前考虑到第几个运动
count   已选运动个数
sum     当前卡路里和

2. 选择是什么？

对第 index 个运动：

  • ✅ 选它

  • ❌ 不选它

这是一个典型的二叉决策树

                index=0
              /         \
           选0            不选0
          /                  \
       index=1              index=1

3. 终止条件（剪枝）

这是 DFS 的灵魂：

✅ 成功条件

count == k 且 sum == t

❌ 失败剪枝

count > k
sum > t
index == n（走完了）

代码

public class LostWeight {
    static int n, k, t;
    static int[] arr;
    static int result = 0;

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

        n = sc.nextInt();
        t = sc.nextInt();
        k = sc.nextInt();

        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 算法：dfs，从第0个运动开始搜索
        dfs(0, 0, 0);

        System.out.println(result);
    }

    /**
     * @param index 当前选到了第几个运动
     * @param count 已经选了运动个数
     * @param sum   已经选的运动卡路里之和
     */
    static void dfs(int index, int count, int sum) {
        // 完成条件
        if (count == k && sum == t) {
            result++;
            return;
        }

        // 剪枝条件
        if (count > k || index == n || sum > t) {
            return;
        }

        // 选当前运动
        dfs(index + 1, count + 1, sum + arr[index]);

        // 不选当前运动
        dfs(index + 1, count, sum);

    }
}