

Cho dãy a1, a2, ..., an (với an là số tự nhiên). Tìm các dãy con của dãy có tổng bằng S Yêu cầu: Viết chương trình tìm dãy con theo yêu cầu của bài toán. Dữ liệu vào: - Dòng 1: ghi số nguyên dương n (1<n<30) và số S (1<S<1000) cách nhau bởi 1 khoảng trắng. - Dòng 2: Gồm n số của dãy a1, a2, …, an. Mỗi số được ghi cách nhau bởi một khoảng trắng. Dư liệu ra: Ghi file văn bản DAYCON.OUT gồm nhiều dòng ghi các giá trị ai sao cho tổng bằng S, mỗi số cách nhau bởi 1 khoảng trắng trong trường hợp không tìm được dãy con thì ghi giá trị bằng -1. Ví dụ:
DAYCON.INP: 7 9
1 2 5 4 10 3 6
DAYCON.OUT:
1 2 6
1 5 3
2 4 3
5 4
3 6
sử dụng ngôn ngữ c++
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
void findSubsets(int index, int currentSum, int targetSum, vector<int>& nums, vector<int>& currentSubset, vector<vector<int>>& result) {
// Nếu tổng hiện tại bằng tổng mục tiêu, lưu dãy con hiện tại
if (currentSum == targetSum) {
result.push_back(currentSubset);
return;
}
// Nếu tổng hiện tại vượt quá tổng mục tiêu hoặc đã duyệt hết các phần tử
if (currentSum > targetSum || index == nums.size()) {
return;
}
// Duyệt từng phần tử từ vị trí index
for (int i = index; i < nums.size(); i++) {
currentSubset.push_back(nums[i]); // Thêm phần tử vào dãy con hiện tại
findSubsets(i + 1, currentSum + nums[i], targetSum, nums, currentSubset, result); // Gọi đệ quy với phần tử tiếp theo
currentSubset.pop_back(); // Loại bỏ phần tử cuối để quay lui
}
}
int main() {
ifstream input("DAYCON.INP");
ofstream output("DAYCON.OUT");
int n, S;
input >> n >> S;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
input >> nums[i];
}
vector<vector<int>> result;
vector<int> currentSubset;
// Tìm tất cả các dãy con có tổng bằng S
findSubsets(0, 0, S, nums, currentSubset, result);
// Nếu không tìm thấy dãy con nào, ghi -1
if (result.empty()) {
output << -1 << endl;
} else {
// Sắp xếp và ghi các dãy con
sort(result.begin(), result.end());
for (const auto& subset : result) {
for (int i = 0; i < subset.size(); i++) {
output << subset[i] << (i < subset.size() - 1 ? " " : "");
}
output << endl;
}
}
input.close();
output.close();
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin