# Hướng Dẫn
## Mô tả bài toán
Bài toán yêu cầu kiểm tra xem có tồn tại một tập con của mảng A có tổng bằng k hay không. Ta có thể giải quyết bằng cách sử dụng phương pháp duyệt tất cả các tập con có thể.
## Giải thích thuật toán
1. **Đọc đầu vào**: Đầu tiên, chương trình đọc số lượng phần tử `n` và giá trị `k` từ đầu vào, sau đó đọc mảng `a` có `n` phần tử.
2. **Duyệt tất cả các tập con**:
- Sử dụng vòng lặp từ `0` đến `2^n - 1` để duyệt qua tất cả các tập con có thể của mảng `a`. Mỗi số nguyên trong khoảng này đại diện cho một tập con.
- Sử dụng phép toán bit để kiểm tra xem phần tử nào thuộc tập con hiện tại.
3. **Tính tổng**: Với mỗi tập con, tính tổng các phần tử thuộc tập con đó.
4. **Kiểm tra điều kiện**: Nếu tổng của tập con bằng `k`, đặt biến `check` thành `true` và thoát khỏi vòng lặp.
5. **In kết quả**: Sau khi duyệt qua tất cả các tập con, nếu `check` là `true`, in "YES", ngược lại in "NO".
## Độ phức tạp
- **Thời gian**: O(2^n) do ta phải duyệt qua tất cả các tập con có thể.
- **Không gian**: O(n) để lưu mảng đầu vào.
## Code
```cpp
/*
author: longvuu
github: kuronight29
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n, k;
cin >> n >> k;
ll a[n];
for(ll i = 0; i < n; i++){
cin >> a[i];
}
bool check = false;
for(ll i = 0; i < (1 << n); i++){
ll sum = 0;
for(ll j = 0; j < n; j++){
if(i & (1 << j)){
sum += a[j];
}
}
if(sum == k){
check = true;
break;
}
}
if(check){
cout << "YES";
}else{
cout << "NO";
}
return 0;
}
```
# GIẢI BÀI "TỔNG TẬP CON" BẰNG ĐỆ QUY
## 🚩 Ý tưởng đệ quy
Tại mỗi vị trí `i`, ta có hai lựa chọn:
1. **Không chọn** phần tử `a[i]`
2. **Chọn** phần tử `a[i]` (nếu `k >= a[i]`) vào tổng
-----------------------------------------------------------------------------------------------
## 🚩 CODE mẫu
```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool tapcon(ll i, ll k, const vector <ll>& a){
if (k==0) return true;
if (i==a.size()) return false;
if (tapcon(i+1,k,a)) return true;
if (k >= a[i])
if (tapcon(i + 1, k - a[i], a))
return true;
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,k; cin>>n>>k;
vector <ll> a(n);
for(int i=0; i<n; i++) cin>>a[i];
if (tapcon(0,k,a))
cout << "YES";
else
cout << "NO";
return 0;
}
```
-----------------------------------------------------------------------------------------------
## 🚩 Giải thích
* nếu (k == 0) => trả về true do tổng các phần tử đã chọn hiện tại bằng đúng k -> tìm được tập con thỏa mãn.
* nếu (i==a.size()) => duyệt hết mảng mà không tìm được nên trả về false.
* nếu chưa chọn được phần tử a[i]
* gọi tiếp đệ quy
`
tapcon(i+1,k,a)
`
* giải thích: tiếp tục tăng lên để tìm phần tử tiếp theo, k giữ nguyên
* nếu tìm được phần tử a[i] rồi
* gọi tiếp đệ quy
`
tapcon(i + 1, k - a[i], a)
`
* giải thích: trừ a[i] khỏi k (vì đã tìm được), tăng i rồi tiếp tục tìm trong phần còn lại với k - a[i]
###### happy coding :D
longvuuu
Created at
23 likes
PeTram2k9
Created at
0 likes