【华为机试】2023年真题B卷（python）-代表团坐车

一、题目

题目描述：

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

约束:

1.一个团只能上一辆车，并且代表团人数(代表团数量小于30，每人代表团人数小于30)小于汽车容量(汽车容量小于100)

2.需要将车辆坐满

二、输入输出

输入描述:
第一行 代表团人数，英文逗号隔开，代表团数量小于30，每个代表团人数小于30
第二行 汽车载客量，汽车容量小于100
输出描述:

坐满汽车的方案数量 如果无解输出0

三、示例

示例1：?
输入：
5,4,2,3,2,4,9

10?
输出：
4

说明：以下几种方式都可以坐满车，[2,3 5]、[2,4,4]、[2,3,5]、[2,4,4]

四、要求

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++262144K，其他语言524288K
64bit IO Format：%lld

五、解题思路

使用回溯法

六、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-代表团坐车.py
@Time    :   2023/12/10 00:09:00
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import sys
# import re
# import re
# import functools
# from collections import Counter, defaultdict
# import copy
# from itertools import permutations
# import math
# import queue
# from queue import Queue


count = 0
def findTargetSumWays(nums, target):
    global count
    backtrack(nums, target, 0, 0);
    return count;


def backtrack(nums, target, index,sum_val):
    global count
    if (index == len(nums)):
        if (sum_val == target):
            count+=1

    else:
        backtrack(nums, target, index + 1, sum_val + nums[index]);
        backtrack(nums, target, index + 1, sum_val);


nums = [int(x) for x in input().split(",")]
target = int(input())
print(findTargetSumWays(nums, target))