พิมพ์จำนวนเต็มที่ไม่ซ้ำจากผลบวก K ตัวจากอาร์เรย์ N ตัวใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ N จำนวนเต็ม และตัวเลข K ต้องพิมพ์จำนวนเต็มที่ไม่ซ้ำกันที่ได้จากการบวก K ตัวจากอาร์เรย์ (เลือกซ้ำได้)

ตัวอย่าง

Input: array = {2, 5, 13, 9}, K = 2
Output: 4 7 10 11 14 15 18 22 26
Explanation: 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

วิธีแก้ปัญหา (Recursion + Set)

ใช้ Recursion สร้างผลรวม K ตัว
เก็บผลลัพธ์ใน set<int> เพื่อกรองซ้ำและเรียงอัตโนมัติ
พิมพ์ค่าทั้งหมดใน set

ตัวอย่างโค้ด C++

#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;
}

ผลลัพธ์ (Output)

The 9 distinct integers are:
4 7 10 11 14 15 18 22 26