dùng qhd c++ làm càng đơn giản càng tốt ạ

2024-12-04 02:39:21

This anwser using AI, please

Dưới đây là giải pháp bằng C++ để tìm một dãy con (không nhất thiết phải liên tiếp) có tổng bằng S từ một dãy số. Mã nguồn sẽ thực hiện điều này một cách đơn giản và hiệu quả.

```cpp
#include
#include

using namespace std;

bool findSubsetSum(const vector& nums, int n, int target, vector& indices) {
if (target == 0) {
return true;
}
if (n == 0) {
return false;
}

// Không chọn phần tử cuối cùng
if (findSubsetSum(nums, n - 1, target, indices)) {
return true;
}

// Chọn phần tử cuối cùng
if (nums[n - 1] <= target) {
indices.push_back(n - 1); // Lưu chỉ số phần tử đã chọn
if (findSubsetSum(nums, n - 1, target - nums[n - 1], indices)) {
return true;
}
indices.pop_back(); // Nếu không tìm thấy, loại bỏ chỉ số đã chọn
}
return false;
}

int main() {
int n, S;
cin >> n >> S;

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

vector indices;
if (findSubsetSum(nums, n, S, indices)) {
cout << "YES" << endl;
for (int idx : indices) {
cout << nums[idx] << " ";
}
cout << endl;
} else {
cout << "NO" << endl;
}

return 0;
}
```

### Giải thích chi tiết:

1. Hàm `findSubsetSum`:
- Hàm này sử dụng đệ quy để kiểm tra xem có thể chọn một dãy con từ mảng `nums` với tổng bằng `target`.
- Nếu `target` bằng 0, nghĩa là đã tìm được một dãy con hợp lệ, hàm trả về `true`.
- Nếu không còn phần tử nào (`n == 0`) mà `target` vẫn khác 0, thì trả về `false`.
- Hàm kiểm tra hai trường hợp: không chọn phần tử cuối cùng và chọn phần tử cuối cùng. Nếu chọn, cần giảm `target` đi giá trị phần tử đó và lưu lại chỉ số của nó trong `indices`.

2. Hàm `main`:
- Nhập vào số lượng phần tử `n` và tổng `S`.
- Đọc các phần tử vào mảng `nums`.
- Gọi hàm `findSubsetSum` để tìm dãy con với tổng bằng `S`.
- Nếu tìm thấy, in "YES" và in các phần tử của dãy con. Ngược lại, in "NO".

### Lưu ý:
- Giả sử `n <= 100` và mỗi giá trị của phần tử không vượt quá 100, thuật toán chạy hiệu quả.
- Độ phức tạp thời gian là O(2^n) nên có thể mở rộng cho các bài toán nhỏ, nhưng không nên cho các bài toán lớn hơn nhiều.

Post Reply