c++ - c++数组所有可能的组合

Question

我的问题是我有 14 位数字的数组我想要一个可以提供所有可能的程序

8位数字之和为40的组合

例如

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