【双机位A卷】华为OD笔试之【回溯/DP】双机位A-小明减肥【Py/Java/C++/C/JS/Go六种语言】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

1036人浏览 · 2025-10-13 17:10:57

闭着眼睛学算法 · 2025-10-13 17:10:57 发布

可上欧弟OJ系统练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

在这里插入图片描述

题目描述与示例

题目描述

小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t。

k，t，n都是给定的。求出可行解数量。

输入描述

第一行输入 n t k，用空格进行分割

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

输出描述

求出可行解数量

补充说明

0 < n < 10
t > 0, 0 < k <= n
每个运动量的卡路里 > 0

示例

输入

4 3 2
1 1 2 3

输出

说明

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

解题思路

回溯方法

注意到本题的数据量很小，0 < n < 10。很容易想到可以用回溯来枚举所有的组合。

这些组合存在两个限制条件，一是组合的和为t，二是选择的数量为k。

那么，类似于 LeetCode39. 组合总数的做法，我们在原先的限制条件上，多加上一个关于选择数量的条件。因此核心的回溯函数为

# 回溯算法框架
def backtrack(nums, t, k, start_idx, cur_num, cur_sum):
    global ans
    # 递归终止条件1
    # 如果当前已经选择的运动数量等于k，并且当前消耗的总卡路里数等于t，则找到了一种方案
    if cur_num == k and cur_sum == t:
        ans += 1
        return
    # 递归终止条件2，同时也是剪枝
    # 如果当前已经选择的运动数量大于k，
    # 或者当前消耗的总卡路里数大于t，
    # 则不可能找到满足条件的方案，直接返回
    if cur_num > k or cur_sum > t:
        return
    # 遍历所有可选的运动
    # 从start_idx开始，避免重复选择
    for i in range(start_idx, len(nums)):
        # 递归调用回溯函数，选择下一个运动
        # 下一层递归的起始选择位置为i+1
        # 当前已经选择的运动数量加1，
        # 当前消耗的总卡路里数需要加上当前选择的运动消耗的卡路里数量
        backtrack(nums, t, k, i+1, cur_num+1, cur_sum+nums[i])

dp方法

回溯并不是本题的最佳做法，只是因为更加套路化和模板化，显得更加简单。

如果本题的数据量更大，则回溯做法会超时。

由于本题的设问是求方法数而并非具体的组合情况，所以我们可以将其看成是一个背包问题来解决。

和常规的路径无关01背包问题相比，本题增加了所选择元素个数必须为k个的条件限制。

如果先不考虑这个条件限制，我们可以直接套用路径无关01背包的1维dp数组模板来解决这个问题。

# dp[i]表示总卡路里数为i的方法数
# dp[t]表示总卡路里数为t的方法数，为答案
dp = [0] * (t+1)
# 初始化dp[0]为1，表示总卡路里数为0的方法数为1种，即不取任何元素
dp[0] = 1

# 先正序遍历物品
for num in nums:
    # 后逆序遍历背包
    # 逆序遍历范围 [0, t - num] 对应的卡路里数为 pre_num 时方法数 dp[pre_num]
    for pre_num in range(t - num, -1, -1):
        # 考虑加上当前卡路里数num的 pre_num + num 所对应的方案数 dp[pre_num + num]
        # 应该递增 dp[pre_num] 种方案数
        dp[num + pre_num] += dp[pre_num]

现在将限制条件考虑上。

我们可以多设置一个维度，来表示当前一共选择了多少个元素。

即，可以使用dp[i][j]来表示选择了j个元素，总卡路里数为i的方法数。

显然，我们将修改动态转移方程为

dp[num + pre_num][j] += dp[pre_num][j-1]

即我们在已经选择了j-1个元素，总卡路里数为pre_num的基础上，多选择了num这个元素，则将前者的方法数dp[pre_num][j-1]更新到选择了j个元素，总卡路里数为num+pre_num的方法数dp[num+pre_num][j]上。

再加上关于j的循环，整体代码将修改为

# 先正序遍历物品
for num in nums:
    # 后逆序遍历背包
    for pre_num in range(t - num, -1, -1):
        # 遍历所选择的元素个数
        # 注意此处j = 0是取不到的，j最小取到1
        for j in range(1, k+1):
            # 考虑选择 j 个元素，加上当前卡路里数 num 的 pre_num + num 所对应的方案数 dp[pre_num + num][j]
            # 应该递增 dp[pre_num][j-1] 种方案数
            dp[num + pre_num][j] += dp[pre_num][j-1]

代码

解法一：回溯

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：【回溯】2025B/2025C/双机位A-小明减肥
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：回溯
# 代码看不懂的地方，请直接在群上提问


# 回溯算法框架
def backtrack(nums, t, k, start_idx, cur_num, cur_sum):
    global ans
    # 递归终止条件1
    # 如果当前已经选择的运动数量等于k，并且当前消耗的总卡路里数等于t，则找到了一种方案
    if cur_num == k and cur_sum == t:
        ans += 1
        return
    # 递归终止条件2，同时也是剪枝
    # 如果当前已经选择的运动数量大于k，
    # 或者当前消耗的总卡路里数大于t，
    # 则不可能找到满足条件的方案，直接返回
    if cur_num > k or cur_sum > t:
        return
    # 遍历所有可选的运动
    # 从start_idx开始，避免重复选择
    for i in range(start_idx, len(nums)):
        # 递归调用回溯函数，选择下一个运动
        # 下一层递归的起始选择位置为i+1
        # 当前已经选择的运动数量加1，
        # 当前消耗的总卡路里数需要加上当前选择的运动消耗的卡路里数量
        backtrack(nums, t, k, i+1, cur_num+1, cur_sum+nums[i])


# 输入运动的数量n，目标总卡路里数t，可选运动数量
n, t, k = map(int, input().split())
# 输入每种运动消耗的卡路里数量nums
nums = list(map(int, input().split()))

# 组合总数，初始化为0
ans = 0

# 调用回溯函数，从第一个运动开始选择
# 当前已经选择的运动数量为0
# 当前消耗的总卡路里数为0
backtrack(nums, t, k, 0, 0, 0)

print(ans)

Java

import java.util.*;

public class Main {
    static int ans = 0; // 记录方案总数

    // 回溯函数
    public static void backtrack(int[] nums, int t, int k, int startIdx, int curNum, int curSum) {
        // 递归终止条件1：恰好选了k个运动，且总卡路里数恰好为t
        if (curNum == k && curSum == t) {
            ans++;
            return;
        }
        // 递归终止条件2：超过k个运动或总卡路里数超过t，剪枝
        if (curNum > k || curSum > t) {
            return;
        }
        // 从startIdx开始，避免重复选择
        for (int i = startIdx; i < nums.length; i++) {
            // 下一层递归：已选运动数+1，卡路里总和加上当前运动
            backtrack(nums, t, k, i + 1, curNum + 1, curSum + nums[i]);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入 n, t, k
        int n = scanner.nextInt();
        int t = scanner.nextInt();
        int k = scanner.nextInt();
        // 输入每个运动的卡路里消耗
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 从第0个运动开始，当前选择数=0，总消耗=0
        backtrack(nums, t, k, 0, 0, 0);
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int ans = 0; // 记录方案总数

// 回溯函数
void backtrack(const vector<int>& nums, int t, int k, int startIdx, int curNum, int curSum) {
    // 递归终止条件1：恰好选了k个运动，且总卡路里数恰好为t
    if (curNum == k && curSum == t) {
        ans++;
        return;
    }
    // 递归终止条件2：超过k个运动或总卡路里数超过t，剪枝
    if (curNum > k || curSum > t) {
        return;
    }
    // 从startIdx开始，避免重复选择
    for (int i = startIdx; i < nums.size(); i++) {
        // 下一层递归：已选运动数+1，卡路里总和加上当前运动
        backtrack(nums, t, k, i + 1, curNum + 1, curSum + nums[i]);
    }
}

int main() {
    int n, t, k;
    cin >> n >> t >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    // 从第0个运动开始，当前选择数=0，总消耗=0
    backtrack(nums, t, k, 0, 0, 0);
    cout << ans << endl;
    return 0;
}

C

#include <stdio.h>

// 全局变量，用于记录方案总数
int ans = 0;

// 回溯函数
void backtrack(int nums[], int n, int t, int k, int startIdx, int curNum, int curSum) {
    // 递归终止条件1：恰好选了k个运动，且总卡路里数恰好为t
    if (curNum == k && curSum == t) {
        ans++;
        return;
    }
    // 递归终止条件2：超过k个运动或总卡路里数超过t，剪枝
    if (curNum > k || curSum > t) {
        return;
    }
    // 从startIdx开始，避免重复选择
    for (int i = startIdx; i < n; i++) {
        // 下一层递归：已选运动数+1，卡路里总和加上当前运动
        backtrack(nums, n, t, k, i + 1, curNum + 1, curSum + nums[i]);
    }
}

int main() {
    int n, t, k;
    scanf("%d %d %d", &n, &t, &k);
    int nums[50]; // 根据实际情况，假设最多有50个运动

    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 从第0个运动开始，当前选择数=0，总消耗=0
    backtrack(nums, n, t, k, 0, 0, 0);

    printf("%d\n", ans);
    return 0;
}

Node JavaScript

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let inputLines = [];
rl.on("line", function (line) {
  inputLines.push(line);
}).on("close", function () {
  // 解析输入
  const [n, t, k] = inputLines[0].split(" ").map(Number);
  const nums = inputLines[1].split(" ").map(Number);

  let ans = 0; // 记录方案总数

  // 回溯函数
  function backtrack(startIdx, curNum, curSum) {
    // 递归终止条件1：恰好选了k个运动，且总卡路里数恰好为t
    if (curNum === k && curSum === t) {
      ans++;
      return;
    }
    // 递归终止条件2：超过k个运动或总卡路里数超过t，剪枝
    if (curNum > k || curSum > t) {
      return;
    }
    // 从startIdx开始，避免重复选择
    for (let i = startIdx; i < nums.length; i++) {
      // 下一层递归：已选运动数+1，卡路里总和加上当前运动
      backtrack(i + 1, curNum + 1, curSum + nums[i]);
    }
  }

  // 从第0个运动开始，当前选择数=0，总消耗=0
  backtrack(0, 0, 0);
  console.log(ans);
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

var ans int // 记录方案总数

// 回溯函数
func backtrack(nums []int, t int, k int, startIdx int, curNum int, curSum int) {
        // 递归终止条件1：恰好选了k个运动，且总卡路里数恰好为t
        if curNum == k && curSum == t {
                ans++
                return
        }
        // 递归终止条件2：超过k个运动或总卡路里数超过t，剪枝
        if curNum > k || curSum > t {
                return
        }
        // 从startIdx开始，避免重复选择
        for i := startIdx; i < len(nums); i++ {
                // 下一层递归：已选运动数+1，卡路里总和加上当前运动
                backtrack(nums, t, k, i+1, curNum+1, curSum+nums[i])
        }
}

func main() {
        reader := bufio.NewReader(os.Stdin)
        // 读取第一行
        line1, _ := reader.ReadString('\n')
        line1 = strings.TrimSpace(line1)
        params := strings.Split(line1, " ")
        n, _ := strconv.Atoi(params[0])
        t, _ := strconv.Atoi(params[1])
        k, _ := strconv.Atoi(params[2])

        // 读取第二行
        line2, _ := reader.ReadString('\n')
        line2 = strings.TrimSpace(line2)
        numStrs := strings.Split(line2, " ")
        nums := make([]int, n)
        for i := 0; i < n; i++ {
                nums[i], _ = strconv.Atoi(numStrs[i])
        }

        ans = 0
        // 从第0个运动开始，当前选择数=0，总消耗=0
        backtrack(nums, t, k, 0, 0, 0)
        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(k*C(n, k))。在n个元素中挑出k个元素作为组合，组合数为C(n, k)，此为状态树最多的叶子节点数，而状态树的高度为k。

空间复杂度：O(1)。不考虑编译栈所占空间，仅需使用若干常数。

解法二：背包dp

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：【回溯】2025B/2025C/双机位A-小明减肥
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：背包dp
# 代码看不懂的地方，请直接在群上提问

# 输入运动的数量n，目标总卡路里数t，可选运动数量
n, t, k = map(int, input().split())
# 输入每种运动消耗的卡路里数量nums
nums = list(map(int, input().split()))

# 初始化大小为(t+1)*(k+1)的二维数组dp
# dp[i][j]表示选择了j个元素，总卡路里数为i的方法数
# dp[t][k]表示选择了k个元素，总卡路里数为t的方法数，即为答案

dp = [[0] * (k+1) for _ in range(t+1)]

# 初始化dp[0][0]为1，表示在不取任何元素的情况且总卡路里数为0的方法数，有且只有1种
dp[0][0] = 1

# 先正序遍历物品
for num in nums:
    # 后逆序遍历背包
    for pre_num in range(t - num, -1, -1):
        # 遍历所选择的元素个数
        # 注意此处j = 0是取不到的，j最小取到1
        for j in range(1, k+1):
            # 考虑选择 j 个元素，加上当前卡路里数 num 的 pre_num + num 所对应的方案数 dp[pre_num + num][j]
            # 应该递增 dp[pre_num][j-1] 种方案数
            dp[num + pre_num][j] += dp[pre_num][j-1]

# 输出答案
print(dp[t][k])

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入 n, t, k
        int n = sc.nextInt();
        int t = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        // 输入每种运动消耗的卡路里
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // dp[i][j] 表示选择 j 个运动，消耗总卡路里为 i 的方案数
        int[][] dp = new int[t + 1][k + 1];

        // 不选任何运动，总卡路里为 0，方案数为 1
        dp[0][0] = 1;

        // 遍历所有运动
        for (int num : nums) {
            // 逆序遍历背包容量，避免重复选取
            for (int preSum = t - num; preSum >= 0; preSum--) {
                // 遍历选择的个数
                for (int j = 1; j <= k; j++) {
                    dp[preSum + num][j] += dp[preSum][j - 1];
                }
            }
        }

        // 输出答案
        System.out.println(dp[t][k]);
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, t, k;
    cin >> n >> t >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // dp[i][j] 表示选择 j 个运动，总卡路里为 i 的方案数
    vector<vector<int>> dp(t + 1, vector<int>(k + 1, 0));

    // 初始化：不选任何运动，总卡路里为 0，方案数为 1
    dp[0][0] = 1;

    // 遍历所有运动
    for (int num : nums) {
        // 从后往前遍历，防止重复选取
        for (int preSum = t - num; preSum >= 0; preSum--) {
            for (int j = 1; j <= k; j++) {
                dp[preSum + num][j] += dp[preSum][j - 1];
            }
        }
    }

    // 输出答案
    cout << dp[t][k] << endl;
    return 0;
}

C

#include <stdio.h>
#include <string.h>

#define MAX_T 1005
#define MAX_K 105

int dp[MAX_T][MAX_K]; // dp[i][j] 表示选择 j 个运动，总卡路里为 i 的方案数

int main() {
    int n, t, k;
    scanf("%d %d %d", &n, &t, &k);
    int nums[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 初始化，表示不选任何运动，总卡路里为 0，方案数为 1
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    // 遍历所有运动
    for (int idx = 0; idx < n; idx++) {
        int num = nums[idx];
        // 从后往前遍历，防止重复选取
        for (int preSum = t - num; preSum >= 0; preSum--) {
            for (int j = 1; j <= k; j++) {
                dp[preSum + num][j] += dp[preSum][j - 1];
            }
        }
    }

    // 输出答案
    printf("%d\n", dp[t][k]);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 创建读取接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
rl.on("line", (line) => {
    inputLines.push(line);
});

rl.on("close", () => {
    // 解析输入
    const [n, t, k] = inputLines[0].split(" ").map(Number);
    const nums = inputLines[1].split(" ").map(Number);

    // dp[i][j] 表示选择 j 个运动，总消耗卡路里为 i 的方案数
    const dp = Array.from({ length: t + 1 }, () => Array(k + 1).fill(0));

    // 初始化：不选任何运动，总消耗为 0，方案数为 1
    dp[0][0] = 1;

    // 遍历每个运动
    for (const num of nums) {
        // 从后往前遍历，防止重复选择
        for (let preSum = t - num; preSum >= 0; preSum--) {
            for (let j = 1; j <= k; j++) {
                dp[preSum + num][j] += dp[preSum][j - 1];
            }
        }
    }

    // 输出答案
    console.log(dp[t][k]);
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

func main() {
        reader := bufio.NewReader(os.Stdin)

        // 读取第一行，解析 n, t, k
        line1, _ := reader.ReadString('\n')
        parts := strings.Fields(line1)
        n, _ := strconv.Atoi(parts[0])
        t, _ := strconv.Atoi(parts[1])
        k, _ := strconv.Atoi(parts[2])

        // 读取第二行，解析每个运动消耗的卡路里
        line2, _ := reader.ReadString('\n')
        numStrs := strings.Fields(line2)
        nums := make([]int, n)
        for i := 0; i < n; i++ {
                nums[i], _ = strconv.Atoi(numStrs[i])
        }

        // dp[i][j] 表示选择 j 个运动，总卡路里为 i 的方案数
        dp := make([][]int, t+1)
        for i := range dp {
                dp[i] = make([]int, k+1)
        }

        // 初始化：不选任何运动，总卡路里为 0，方案数为 1
        dp[0][0] = 1

        // 遍历所有运动
        for _, num := range nums {
                // 从后往前遍历防止重复选择
                for preSum := t - num; preSum >= 0; preSum-- {
                        for j := 1; j <= k; j++ {
                                dp[preSum+num][j] += dp[preSum][j-1]
                        }
                }
        }

        // 输出答案
        fmt.Println(dp[t][k])
}

时空复杂度

时间复杂度：O(nkt)。三重循环所需时间复杂度

空间复杂度：O(tk)。dp数组所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接OD真题汇总(持续更新)
绿色聊天软件戳 od1441或了解更多

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

【AI】-7 从知识库到 AI Agent -进阶

AI Agent技术社区

AI Agent 面试题 353：A2A协议的服务发现和注册机制详解

A2A 协议是 AI Agent 技术体系中的重要组成部分。简单来说，它涉及到 Agent 如何在工具使用与函数调用层面实现智能化的行为和决策。在实际应用中，A2A 协议的核心目标是让 Agent 能够更加高效、准确地完成特定任务。这需要我们深入理解其底层原理和实现机制。从学术角度来看，A2A 协议的研究可以追溯到人工智能的早期阶段。早在 1950 年代，Alan Turing 就提出了

AI Agent技术社区

英伟达AI刷爆ARC-AGI-3！AVO Harness架构让Agent从30%飙升到100%

AI Agent技术社区

所有评论(0)

查看更多评论

闭着眼睛学算法

@weixin_48157259

已为社区贡献4条内容

【双机位A卷】华为OD笔试之【回溯/DP】双机位A-小明减肥【Py/Java/C++/C/JS/Go六种语言】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

补充说明

示例

输入

输出

说明

解题思路

回溯方法

dp方法

代码

解法一：回溯

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

解法二：背包dp

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练

所有评论(0)

闭着眼睛学算法

【双机位A卷】华为OD笔试之【回溯/DP】双机位A-小明减肥【Py/Java/C++/C/JS/Go六种语言】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

补充说明

示例

输入

输出

说明

解题思路

回溯方法

dp方法

代码

解法一：回溯

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

解法二：背包dp

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练

所有评论(0)

温馨提示：您尚未绑定手机号

闭着眼睛学算法