合計がkになる部分集合が存在しないように数値を選択するC++プログラム

2つの整数 n と k が与えられます。1から n までの範囲に含まれる相異なる要素の中から、「合計が k に等しくなる部分集合が一つも存在しない」という条件を満たすように、できるだけ多くの要素を選びます。そして、そのような選び方が見つかる場合は、選んだ数値を出力します。

例えば、入力が n = 5、k = 3 の場合、出力は [4, 5, 2] となります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

i を (k + 1) / 2 から k - 1 まで1ずつ増やしながら繰り返す：
    i を出力する
i を k + 1 から n まで1ずつ増やしながら繰り返す：
    i を出力する

このアルゴリズムのポイントは、(k + 1) / 2 以上 k 未満の数値と、k より大きい数値を選ぶことです。k より大きい数値は、それ単独でも他の数値との組合せでも、必ず合計が k を超えるため候補になりません。また、(k + 1) / 2 以上の数値を2つ以上足し合わせると必ず k を超えるため、結果的に合計がちょうど k になる部分集合は存在しなくなります。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

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

入力

5, 3

出力

2, 4, 5,