更有效地找到具有相同总和的所有组合

学习cpp

我想找到 -n 到 n 范围内四个数字的所有组合，这些数字加起来为零。有没有有效的算法来解决这个问题？

#include <iostream>
using namespace std;

int main()
{
    int i, j, k, l;
    int size = 20;

    for (i = -size; i <= size; i++)
    {
        for (j = -size; j <= size; j++)
        {
            for (k = -size; k <= size; k++)
            {
                for (l = -size; l <= size; l++)
                {
                    if (i + j + k + l == 0)
                    {
                        cout << i << " " << j << " " << " " << k << " " << l << endl;
                    }
                }
            }

        }
    }
    return 0;

}

胡尔希德·诺穆拉多夫

查看我的代码和评论。算法效率是O(N^3)，解的总数也是O(N^3)。

#include <cstdio>
#include <algorithm>


int main(){
      int size = 20;
       for(int a = -size; a <= size; ++a){
            for(int b = -size; b <= size; ++b ) {
                 int c_min, c_max, d, c;
                 //1.  a + b + c +d = 0.
                 //2.  d = -(a+b+c)   
                 //3.   -size <= d <= size
                 //4.  -size <= -(a+b+c) <= size
                 //5.  size >= a +b + c >= -size
                 //6.  -size - (a+b) <= c <= size - (a+b)
                 //7. but,    -size <= c <= size.
                c_min = std::max(-size, -size - (a+b) ) ;
                c_max = std::min(size, size - (a+b) ) ;
                for(c = c_min ; c <= c_max; ++c){
                      d = -(a+b+c);
                      printf("a = %d b = %d  c = %d  d= %d\n", a,b,c,d);                          
                }
            }
       }

   return 0;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。