c++ - 如何在给定数组中找到所有匹配的数字，总和为 'N'

Question

我的目标是找到总和为给定总数的所有可能组合。例如，如果数组是 2 59 3 43 5 9 8 62 10 4 如果总数是 12，那么可能的组合是

2 10
3 9
8 4
5 3 4

这是我编写的第一组代码。想知道可以对此进行的最佳改进。

   int find_numbers_matching_sum(int *number_coll, int total)
{

    int *search_till = lower_bound(number_coll,number_coll+TOTAL_SIZE, total);
    int location = search_till - number_coll;
    if (*search_till > total && location > 0 )
    {
        --location;
    }

    while ( location >= 0 )
    {
        find_totals(number_coll,total,location);
        --location;
    }
    return 1;
}

int find_totals(int *number_coll, int total, int end_location)
{
    int left_ones = total - number_coll[end_location];
    int curloc = end_location;
    int *search_till = 0;
    int location ;
    int all_numbers[10];
    int i = 0;

    all_numbers[i] = number_coll[end_location];
    while ( left_ones && curloc >= 0 )
    {
        search_till = lower_bound(number_coll,number_coll+end_location, left_ones);
        location = search_till - number_coll;
        if (*search_till > left_ones && location > 0 )
        {
            --location;
        }
        else if ( left_ones < *search_till )
        {
            break;
        }
        curloc=location;
        left_ones = left_ones - number_coll[curloc];
        all_numbers[++i] = number_coll[curloc];
        end_location = curloc - 1;
    }

    if ( !left_ones )
    {
        while ( i>=0)
        {
            cout << all_numbers[i--] << ' ';
        }
    }
    cout << endl;
    return 1;


}

Answer 1

您描述的问题也称为 Subset Sum Problem这是NP-complete .您可以实现的最好结果是一种指数时间算法，该算法会尝试您的数组/集合的所有可能子集。