C言語プログラムで合計がk以下となるトリプレット（3つ組）を出力する方法

要素の集合を含む配列が与えられたとき、その中から合計がk以下となるちょうど3つの要素の組み合わせ（トリプレット）をすべて見つけ出すことが課題です。

問題の例

入力： arr[] = {1, 2, 3, 8, 5, 4}

出力： {1, 2, 3} {1, 2, 5} {1, 2, 4} {1, 3, 5} {1, 3, 4} {1, 5, 4} {2, 3, 5} {2, 3, 4}

この問題では、まず配列のサイズを計算します。そして、そのサイズをもとに、外側のループ変数 i は size-2 未満まで、中間のループ変数 j は size-1 未満まで、内側のループ変数 k は size 未満までそれぞれ繰り返すことで、重複のない3つの要素の組み合わせをすべて網羅的に調べることができます。

アルゴリズム

START
Step 1 → int型変数 sum に閾値 k（例：10）を設定し、i、j、k を宣言する
Step 2 → sizeof(arr)/sizeof(arr[0]) を使って配列のサイズで size を宣言・初期化する
Step 3 → i を 0 から size-2 未満までループ
　　j を i+1 から size-1 未満までループ
　　　　k を j+1 から size 未満までループ
　　　　　　IF arr[i] + arr[j] + arr[k] <= sum ならば
　　　　　　　　arr[i]、arr[j]、arr[k] を出力する
　　　　　　End IF
　　　　End Loop for
　　End Loop For
Step 4 → End Loop For
STOP

サンプルコード

#include <stdio.h>
int main(int argc, char const *argv[]) {
    int arr[] = {1, 2, 3, 8, 5, 4};
    int sum = 10;
    int i, j, k;
    int size = sizeof(arr)/sizeof(arr[0]);
    for (i = 0; i < size-2; i++) {
        for (j = i+1; j < size-1; j++) {
            for (k = j+1; k < size; k++) {
                if( arr[i]+ arr[j] + arr[k] <= sum )
                    printf( "{%d, %d, %d}\n",arr[i], arr[j], arr[k] );
            }
        }
    }
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

{1, 2, 3}
{1, 2, 5}
{1, 2, 4}
{1, 3, 5}
{1, 3, 4}
{1, 5, 4}
{2, 3, 5}
{2, 3, 4}

計算量について

このアプローチでは3つのネストされたループを使用しているため、時間計算量は O(n³) となります。ここで n は配列の要素数です。配列のサイズが大きくなると処理時間が急激に増加するため、大規模なデータに対してはソートと二分探索やツーポインタ手法を組み合わせた最適化が有効です。一方で、この三重ループによる総当たり的な方法は実装が非常にシンプルで理解しやすいため、小規模な配列や学習用途には最適なアプローチといえます。