【C++】各要素の符号を変更して合計がMで割り切れるすべての組み合わせを出力する方法

この記事では、N個の要素からなる配列が与えられたとき、各要素に「+（プラス）」または「−（マイナス）」の符号を付けた合計値が、整数Mで割り切れるようなすべての組み合わせを出力するC++プログラムを解説します。

問題の概要

配列の各要素に対して符号を選ぶ自由度があるため、合計値の候補は複数存在します。その中から、Mで割り切れるものだけを符号付きで出力するのが本問題の目的です。

入力 : array = {4, 7, 3} ; M = 3
出力 :
- 4 + 7 - 3   （合計 = 0）
- 4 + 7 + 3   （合計 = 6）
+ 4 - 7 - 3   （合計 = -6）
+ 4 - 7 + 3   （合計 = 0）

いずれの結果も 0、6、-6 となっており、すべて3で割り切れることが確認できます。

アプローチ：べき集合（Power Set）の活用

この問題を解く鍵となるのはべき集合の概念です。各要素の符号は「+」か「−」の2択なので、N個の要素に対して符号の組み合わせは全部で 2^N 通り存在します。

そこで、0 から 2^N-1 までの整数をビットマスクとして利用します。あるビットが 1 なら対応する要素に「+」を、0 なら「−」を割り当てることで、すべての符号の組み合わせを効率よく列挙できます。

アルゴリズム

Step 1: 0 ～ 2^N - 1 のビットマスクを順に調べ、「+」と「−」のすべての組み合わせを反復処理する。
Step 2: 各組み合わせについて合計値を計算し、その合計がMで割り切れる場合のみ、符号付きで出力する。

C++実装例

#include <iostream>
using namespace std;

// 合計がMで割り切れる符号の組み合わせを出力する関数
void printDivisibleSum(int a[], int n, int m){
    // 2^n 通りのビットマスクをすべて試す
    for (int i = 0; i < (1 << n); i++) {
        int sum = 0;
        int num = 1 << (n - 1);
        for (int j = 0; j < n; j++) {
            if (i & num)
                sum += a[j];       // ビットが1なら「+」
            else
                sum += (-1 * a[j]); // ビットが0なら「−」
            num = num >> 1;
        }
        // 合計がMで割り切れる場合のみ出力
        if (sum % m == 0) {
            num = 1 << (n - 1);
            for (int j = 0; j < n; j++) {
                if ((i & num))
                    cout << "+ " << a[j] << " ";
                else
                    cout << "- " << a[j] << " ";
                num = num >> 1;
            }
            cout << endl;
        }
    }
}

int main(){
    int arr[] = {4,7,3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout<<"Mで割り切れる合計の組み合わせ :\n";
    printDivisibleSum(arr, n, m);
    return 0;
}

実行結果

Mで割り切れる合計の組み合わせ :
- 4 + 7 - 3
- 4 + 7 + 3
+ 4 - 7 - 3
+ 4 - 7 + 3

コードのポイント

• ビットシフトによる全列挙： 外側のループ変数 i を 2進数のビット列とみなし、各ビットが要素ごとの符号に対応します。
• 2段階の走査： 最初の内側ループで合計値を計算し、条件を満たした場合だけもう一度同じビットマスクを使って符号付きの出力を行います。
• 負の数への対応： 剰余演算 sum % m == 0 は合計が負の場合でも正しく機能するため、マイナスの合計も漏れなく判定できます。

計算量

• 時間計算量： O(2^N × N) — すべての符号の組み合わせについて、各要素を1回ずつ調べるためです。
• 空間計算量： O(1) — 追加のデータ構造を使用しないため定数メモリで動作します。

この手法はNが小さい場合（目安として20以下程度）に有効です。Nが大きくなると組み合わせの総数が指数関数的に増えるため、動的計画法などで部分和を管理する最適化も検討するとよいでしょう。