c++ - c++配列すべての可能な組み合わせ

Question

私の問題は、14桁の配列があり、可能な限りすべてを提供するプログラムが欲しいということです。

合計が40になる8桁以内の組み合わせ

例えば

14桁は1,7,7,4,6,5,5,2,4,7,10,3,9,6,

組み合わせはこのようにする必要があります

6+5+6+7+2+3+2+9=40

7+7+7+7+6+4+1+1=40

Answer 1

配列のサイズはちょうど 14 なので、最適化は行いません。を使用してすべての組み合わせを bitwise operations見つけることで、問題を解決できます。

アイデアは次のとおりです。指定された配列 (セット) のすべてのサブセットを生成します。このセットは、べき乗セットとして知られています。サブセット (組み合わせ) のそれぞれについて、サブセットの要素の合計が 40 に等しいかどうかを確認します。いいえ。

Bit Wise Operations を使用してすべての組み合わせを見つける方法については、次のチュートリアルを参照してください。http://www.codechef.com/wiki/tutorial-bitwise-operations

C++ 実装:

int main()
{
  int A[] = { 1, 7, 7, 4, 6, 5, 5, 2, 4, 7, 10, 3, 9, 6 };
  int n = sizeof(A) / sizeof(A[0]);
  int desiredsum = 40;
  int total_soln=0;
  for (int i = 0; i <= (1 << n); ++i)
  {
    vector < int >v;/*The vector contains element of a subset*/
    for (int j = 0; j <= n; ++j)
    {
            if (i & 1 << j)
                    v.push_back(A[j]);
    }
    if (v.size() == 8)/*Check whether the size of the current subset is 8 or not*/
    {       
            //if size is 8, check whether the sum of the elements of the current
        // subset equals to desired sum or not
            int sum = 0;
            for (int j = 0; j < v.size(); ++j)
            {
                    sum += v[j];
            }
            if (sum == desiredsum)
            {
                    for (int j = 0; j < v.size(); ++j)
                    {
                            (j ==
                             v.size() - 1) ? cout << v[j] << "=" : cout << v[j] << "+";
                    }
                    total_soln++;
                    cout << desiredsum << " " << endl;
            }
    }
  }
  cout<<"Total Solutions: "<<total_soln<<endl;
  return 0;
}

IDEONE リンク: http://ideone.com/31jh6c