Giả sử chúng ta có hai số n và k. Chúng ta phải chọn số lượng lớn nhất các phần tử khác nhau từ 1 đến n, sao cho không có tập con nào có tổng bằng k. Nếu tìm được thì trả về các số đã chọn.
Ví dụ, nếu đầu vào là n = 5; k = 3, thì đầu ra sẽ là [4, 5, 2]
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
for khởi tạo i := (k + 1) / 2, khi i <= k - 1, cập nhật (tăng i lên 1), do: in i for khởi tạo i := k + 1, khi i <= n, cập nhật (tăng i lên 1), do: in i
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; void solve(int n, int k) { for (int i = (k + 1) / 2; i <= k - 1; i++) { cout << i << ", "; } for (int i = k + 1; i <= n; i++) { cout << i << ", "; } } int main() { int n = 5; int k = 3; solve(n, k); }Đầu vào
5, 3
Đầu ra
2, 4, 5,