【 华为OD机试 2023】 组装新的数组（C++ Java JavaScript Python）_给你一个整数 m 和数组 n,n 中的元素为连续整数

题目描述

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

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

输入描述

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

输出描述

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

备注

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

用例

题目解析

题目中的组装规则比较复杂，可以考虑使用回溯法来解决。回溯法的基本思路是枚举所有可能的情况，然后逐步排除不符合条件的情况，最终得到符合要求的结果。

在这道题中，我们可以通过枚举数组N中的元素来得到所有可能的情况。具体来说，我们从数组N的第一个元素开始，依次加入到结果数组R中，然后递归处理剩余部分。如果当前的结果数组R中的元素总和已经等于M了，那么这就是一种符合要求的组装办法，我们将其计数即可。如果当前的结果数组R中的元素总和还不足M，那么我们可以继续从数组N中的下一个元素开始递归处理。如果当前的结果数组R中的元素总和已经超过了M，那么这种情况不符合要求，我们需要回溯到上一层，尝试其他的情况。

需要注意的是，题目中要求结果数组R中最多只能有1个不在N中的元素，并且这个元素比N中的数字都要小。因此，在递归处理的过程中，我们需要记录当前结果数组R中最小的元素，然后在后续的递归中，只考虑比这个最小元素大的数字。这样可以保证结果数组R中最多只有1个不在N中的元素，并且这个元素比N中的数字都要小。

C++

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

// 深度优先搜索，index表示从数组的第几个元素开始搜索，sum表示当前已经选取的元素的和，min表示数组中最小的元素
// m表示要组成的和，count表示组装办法的数量
int dfs(vector<int>& arr, int index, int sum, int min, int m, int count) {
    if (sum > m) { // 如果当前已选取的元素和大于m，返回当前组装办法的数量
        return count;
    }
    if (sum == m || (m - sum < min && m - sum > 0)) { // 如果当前已选取的元素和等于m或者m减去当前已选取的元素和小于最小元素且大于0，返回当前组装办法的数量+1
        return count + 1;
    }
    for (int i = index; i < arr.size(); i++) { // 从index开始搜索
        count = dfs(arr, i, sum + arr[i], min, m, count); // 递归搜索下一个元素
    }
    return count;
}

int getResult(vector<int>& arr, int m) {
    arr.erase(remove_if(arr.begin(), arr.end(), [m](int val){return val > m;}), arr.end()); // 只保留比m小的连续整数
    int min = arr[0];
    return dfs(arr, 0, 0, min, m, 0); // 从第一个元素开始搜索
}


int main() {
    vector<string> lines;
    string line;
    while (getline(cin, line)) { // 逐行读入输入
        lines.push_back(line);
        if (lines.size() == 2) { // 如果读入了2行，说明输入结束，开始处理数据
            vector<int> arr;
            string s = lines[0];
            int m = stoi(lines[1]);
            size_t pos = 0;
            while ((pos = s.find(" ")) != string::npos) { // 以空格为分隔符，将字符串s分割成多个整数
                string num = s.substr(0, pos);
                arr.push_back(stoi(num));
                s.erase(0, pos + 1);
            }
            arr.push_back(stoi(s));
            cout << getResult(arr, m) << endl; // 输出组装办法的数量
            lines.clear(); // 清空lines，准备读入下一组数据
        }
    }
    return 0;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

JavaScript

const readline = require('readline');

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

let lines = [];
let arr = [];

function dfs(index, sum, min, m, count) {
  if (sum > m) {
    return count;
  }
  if (sum === m || (m - sum < min && m - sum > 0)) {
    return count + 1;
  }
  for (let i = index; i < arr.length; i++) {
    count = dfs(i, sum + arr[i], min, m, count);
  }
  return count;
}

function getResult(arr, m) {
  arr = arr.filter(val => val <= m);
  const min = arr[0];
  return dfs(0, 0, min, m, 0);
}

rl.on('line', (line) => {
  lines.push(line);
  if (lines.length === 2) {
    const s = lines[0];
    const m = parseInt(lines[1]);
    arr = s.split(' ').map(num => parseInt(num));
    console.log(getResult(arr, m));
    lines = [];
    arr = [];
  }
});
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
29
30
31
32
33
34
35
36
37
38
39
40

Java

import java.util.*;

public class Main {
    // 深度优先搜索，index表示从数组的第几个元素开始搜索，sum表示当前已经选取的元素的和，min表示数组中最小的元素
    // m表示要组成的和，count表示组装办法的数量
    public static int dfs(List<Integer> arr, int index, int sum, int min, int m, int count) {
        if (sum > m) { // 如果当前已选取的元素和大于m，返回当前组装办法的数量
            return count;
        }
        if (sum == m || (m - sum < min && m - sum > 0)) { // 如果当前已选取的元素和等于m或者m减去当前已选取的元素和小于最小元素且大于0，返回当前组装办法的数量+1
            return count + 1;
        }
        for (int i = index; i < arr.size(); i++) { // 从index开始搜索
            count = dfs(arr, i, sum + arr.get(i), min, m, count); // 递归搜索下一个元素
        }
        return count;
    }

    public static int getResult(List<Integer> arr, int m) {
        arr.removeIf(val -> val > m); // 只保留比m小的连续整数
        int min = arr.get(0);
        return dfs(arr, 0, 0, min, m, 0); // 从第一个元素开始搜索
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> lines = new ArrayList<>();
        while (scanner.hasNextLine()) { // 逐行读入输入
            String line = scanner.nextLine();
            lines.add(line);
            if (lines.size() == 2) { // 如果读入了2行，说明输入结束，开始处理数据
                List<Integer> arr = new ArrayList<>();
                String s = lines.get(0);
                int m = Integer.parseInt(lines.get(1));
                String[] nums = s.split(" ");
                for (String num : nums) {
                    arr.add(Integer.parseInt(num));
                }
                System.out.println(getResult(arr, m)); // 输出组装办法的数量
                lines.clear(); // 清空lines，准备读入下一组数据
            }
        }
    }
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

Python

def dfs(arr, index, sum, min_val, m, count):
    if sum > m:
        return count
    if sum == m or (m - sum < min_val and m - sum > 0):
        return count + 1
    for i in range(index, len(arr)):
        count = dfs(arr, i, sum + arr[i], min_val, m, count)
    return count

def get_result(arr, m):
    arr = [x for x in arr if x <= m] # 只保留比m小的连续整数
    min_val = min(arr)
    return dfs(arr, 0, 0, min_val, m, 0)


s = input().strip()
m = int(input().strip())
arr = list(map(int, s.split()))
print(get_result(arr, m))
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20