Trong bài toán này, chúng ta được cung cấp một mảng gồm N số nguyên và một số K. Nhiệm vụ của chúng ta là in tất cả các số riêng biệt có thể được tạo ra bằng cách thêm K phần tử bất kỳ từ mảng. Trong khi chọn bất kỳ số nào có thể được lặp lại K lần.
Hãy lấy một ví dụ để hiểu vấn đề -
Input: array = {2, 5, 13, 9} K = 2
Output: 2,7,15,11,10,18,14,26,22
Explaination: 2 elements added :
2+2=4, 2+5=7, 2+13=15, 2+9=11, 5+5=10, 5+13=18, 5+9=14, 13+13=26, 13+9=22, 9+9=18 Để giải quyết vấn đề này, chúng ta sẽ tìm tất cả các tổ hợp của k phần tử từ mảng. Đối với điều này, chúng tôi sẽ sử dụng đệ quy sẽ được gọi là đệ quy để tạo ra các số. Để tránh các giá trị trùng lặp, chúng tôi sẽ lưu trữ các số trong một tập hợp.
Ví dụ
Mã sẽ hiển thị việc triển khai giải pháp của chúng tôi -
#include <bits/stdc++.h>
using namespace std;
set<int> distNumbers;
void generateNumberFromArray(int count, int arr[], int n, int num, int k) {
if (k == count) {
distNumbers.insert(num);
return;
}
for (int i = 0; i < n; i++) {
generateNumberFromArray(count + 1, arr, n, num + arr[i], k);
}
}
void printDistinctIntegers(int k, int arr[], int n) {
generateNumberFromArray(0, arr, n, 0, k);
cout<<"The "<<distNumbers.size()<<" distinct integers are:\n";
while (!distNumbers.empty()) {
cout << *distNumbers.begin() <<"\t";
distNumbers.erase(*distNumbers.begin());
}
}
int main() {
int arr[]={ 2, 5, 13, 9 };
int n=4;
int k=2;
printDistinctIntegers(k, arr, n);
return 0;
} Đầu ra
The 9 distinct integers are − 4 7 10 11 14 15 18 22 26