C++でN個の整数の配列からK個の数を選んで加算し、生成できるすべての異なる整数を出力する方法

問題の概要

この問題では、N個の整数からなる配列と数値Kが与えられます。求められているのは、配列から任意のK個の要素を選んで加算することで生成できる、すべての異なる整数を出力することです。なお、同じ要素を複数回（最大K回まで）選んでも構いません。

入出力例

入力：array = {2, 5, 13, 9}、K = 2
出力：4, 7, 10, 11, 14, 15, 18, 22, 26

この例では、2つの要素を加算した結果は以下のようになります。

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

重複する値（例えば5+13=18と9+9=18）を除いた結果、9種類の異なる整数が得られます。

解決アプローチ

この問題を解くには、配列からK個の要素を選ぶすべての組み合わせを列挙する必要があります。そのために再帰呼び出しを利用して数値を順次生成していきます。また、同じ値が何度も出力されるのを防ぐため、生成した数値はset（集合）に格納します。setは自動的に重複を排除しソートされた状態で要素を保持するため、最終的に昇順の異なる整数リストを簡単に取得できます。

アルゴリズムの手順

1. 再帰関数に対して、現在選択した要素の個数（count）、現在の合計値（num）を渡す。
2. countがKに達したら、その時点の合計値をsetに挿入して再帰を終了する。
3. そうでなければ、配列の各要素について合計値に加算しながら再帰呼び出しを行う。
4. すべての組み合わせを生成後、setの中身を順番に出力する。

コード実装

以下のコードは、上記の解決策を実装したものです。

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

実行結果

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

計算量について

この手法では、各ステップで配列内のN個の要素すべてを候補として再帰的に展開するため、時間計算量はO(N^K)となります。Kが大きくなると組み合わせの総数が急激に増える点には注意が必要です。一方、setへの挿入・検索は対数時間で行われるため、重複チェックのオーバーヘッドは比較的小さく抑えられます。