2023荣耀校招机试（java&python&C++）组装新的数组

题目

给你一个整数M和数组N，N中的元素为连续整数，要求根据N中的元素组装成新的数组R，组装规则：

1. R中元素总和加起来等于M
2. R中的元素可以从N中重复选取
3. R中的元素最多只能有1个不在N中，且比N中的数字都要小（不能为负数）

备注：

1 ≤ M ≤ 30
1 ≤ N.length ≤ 1000

输入描述

第一行输入是连续数组N，采用空格分隔
第二行输入数字M

输出描述

输出的是组装办法数量，int类型

用例1

输入

2
5

输出

1

说明

只有1种组装办法，就是[2,2,1]

用例2

输入

2 3
5

输出

2

说明

一共两种组装办法，分别是[2,2,1]，[2,3]

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义一个函数，接收一个整数数组和一个目标值m，返回数组中所有小于等于m的元素组合成m的方法数
int getResult(vector<int>& arr, int m) {
  // 创建一个新的数组，存储原数组中小于等于m的元素
  vector<int> newArr;
  for (int val : arr) {
    if (val <= m) {
      newArr.push_back(val);
    }
  }

  // 找到新数组中最小的元素
  int min = *min_element(newArr.begin(), newArr.end());

  // 调用dfs函数，从新数组的第0个元素开始，递归地计算所有可能的组合方法数
  return dfs(newArr, 0, 0, min, m, 0);
}

// 定义一个递归函数，接收一个整数数组，一个索引值，一个当前和值，一个最小值，一个目标值和一个计数器
int dfs(vector<int>& arr, int index, int sum, int min, int m, int count) {
  // 如果当前和大于目标值，则返回计数器
  if (sum > m) {
    return count;
  }

  // 如果当前和等于目标值或者当前和与目标值之差小于最小值且大于0，则返回计数器加一
  if (sum == m || (m - sum < min && m - sum > 0)) {
    return count + 1;
  }

  // 遍历数组中从索引开始到末尾的所有元素，对每个元素调用dfs函数，并更新计数器
  for (int i = index; i < arr.size(); i++) {
    count = dfs(arr, i, sum + arr[i], min, m, count);
  }

   // 返回最终的计数器
   return count;
}

int main() {

   string line;

   // 使用getline函数读取第一行输入作为字符串
   getline(cin,line);

   // 使用stringstream类将字符串转换为流对象
   stringstream ss(line);

   // 创建一个整数向量来存储输入的整数
   vector<int> arr;

   // 使用流提取运算符从流对象中读取每个整数，并将其推入向量中
   int num;
   while(ss >> num){
     arr.push_back(num);
   }

   // 使用cin读取第二行输入作为整数
   cin >> num;

   // 调用getResult函数并打印结果
   cout << getResult(arr,num) << endl;

}

python

import sys  
  
  
def dfs(arr, index, sum, min, m, count):  
    # 递归函数，用于计算所有可能的组合数  
    if sum > m:  
        return count  # 如果当前和大于目标值，返回当前计数  
  
    if sum == m or (m - sum < min and m - sum > 0):  
        return count + 1  # 如果当前和等于目标值，或者剩余空间小于最小值，返回当前计数加一  
  
    for i in range(index, len(arr)):  
        count = dfs(arr, i, sum + arr[i], min, m, count)  # 对每个元素进行递归调用，累加和和计数  
  
    return count  # 返回最终的计数  
  
  
def getResult(arr, m):  
    newArr = []  
    for val in arr:  
        if val <= m:  
            newArr.append(val)  # 过滤掉大于目标值的元素  
  
    minval = min(newArr)  # 找到数组中的最小值  
  
    return dfs(newArr, 0, 0, minval, m, 0)  # 调用递归函数  
  
  
line = input()  # 输入一行数字，以空格分隔  
  
arr = list(map(int, line.split()))  # 将输入转换为整数数组  
  
num = int(input())  # 输入一个整数作为目标值  
  
print(getResult(arr, num))  # 输出结果

JAVA

// 导入必要的包  
import java.util.ArrayList;  
import java.util.Scanner;  
  
// 定义一个类  
public class Main {  
  
    // 定义一个函数，接收一个整数数组列表和一个目标值m，返回数组中所有小于等于m的元素组合成m的方法数  
    public static int getResult(ArrayList<Integer> arr, int m) {  
        // 创建一个新的数组列表，存储原数组中小于等于m的元素  
        ArrayList<Integer> newArr = new ArrayList<>();  
        for (int val : arr) {  
            if (val <= m) {  
                newArr.add(val);  
            }  
        }  
  
        // 找到新数组中最小的元素  
        int min = Integer.MAX_VALUE;  
        for (int val : newArr) {  
            if (val < min) {  
                min = val;  
            }  
        }  
  
        // 调用dfs函数，从新数组的第0个元素开始，递归地计算所有可能的组合方法数  
        return dfs(newArr, 0, 0, min, m, 0);  
    }  
  
    // 定义一个递归函数，接收一个整数数组列表，一个索引值，一个当前和值，一个最小值，一个目标值和一个计数器  
    public static int dfs(ArrayList<Integer> arr, int index, int sum, int min, int m,  
                          int count) {  
        // 如果当前和大于目标值，则返回计数器  
        if (sum > m) {  
            return count;  
        }  
  
        // 如果当前和等于目标值或者当前和与目标值之差小于最小值且大于0，则返回计数器加一  
        if (sum == m || (m - sum < min && m - sum > 0)) {  
            return count + 1;  
        }  
  
        // 遍历数组中从索引开始到末尾的所有元素，对每个元素调用dfs函数，并更新计数器  
        for (int i = index; i < arr.size(); i++) {  
            count = dfs(arr, i, sum + arr.get(i), min, m, count);  
        }  
  
        // 返回最终的计数器  
        return count;  
    }  
  
    public static void main(String[] args) {  
  
        String line;  
  
        // 使用Scanner类读取第一行输入作为字符串  
        Scanner sc = new Scanner(System.in);  
        line = sc.nextLine();  
  
        // 使用split方法将字符串按空格分割为字符串数组，并转换为整数数组列表  
        String[] strArr = line.split(" ");  
        ArrayList<Integer> arr = new ArrayList<>();  
        for (String s : strArr) {  
            arr.add(Integer.parseInt(s));  
        }  
  
        // 使用nextInt方法读取第二行输入作为整数，并关闭Scanner对象  
        int num = sc.nextInt();  
        sc.close();  
  
        // 调用getResult函数并打印结果  
        System.out.println(getResult(arr,num));  
  
    }  
}	

---