Chương trình C ++ để chọn một số số mà sẽ không có tập con nào có tổng là k

Giả sử chúng ta có hai số n và k. Ta phải chọn tối đa số phần tử phân biệt từ 1 đến n sao cho không có tập con nào có tổng bằng k. Nếu chúng tôi có thể tìm thấy thì hãy trả lại các số đã chọn.

Vì vậy, nếu đầu vào giống như n =5; k =3, thì đầu ra sẽ là [4, 5, 2]

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

for initialize i := (k + 1) / 2, when i <= k - 1, update (increase i by 1), do:
   print i
for initialize i := k + 1, when i <= n, update (increase i by 1), do:
   print i

Ví dụ

Hãy cùng chúng tôi xem cách 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,