如何穷举符合条件的数组？求算法

Question

从44、45、46...72、73共有29个数字，每次取10个数，每个数字可以重复取，要求这10个数的和为500，共有多少种情况？

比如：50取出10次就是500算符合情况。44和54各取出5次也算符合的情况，以下这些都算：
50 50 50 50 50 50 50 50 50 50
44 54 44 54 44 54 44 54 44 54
44 44 44 44 44 54 54 54 54 54
47 47 48 48 49 49 51 52 52 57
45 46 47 48 48 49 53 54 55 55
47 47 47 48 49 49 51 53 54 55
其他还有那些符合条件的情况？请穷举出来。

Answer 1

dfs暴搜一下就行，其实剪完枝复杂度不是很大(最深只有10层)，加上输出c++也只要不到10s。

/*----------------------------------*/
/* Author : KaMtuo                  */
/* Email : [e-mail]            */
/* Creation_time : 2022-08-08 20:06 */
/* Software : Visual Studio Code    */
/*----------------------------------*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <map>

#define endl "\n"

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::sort;
using std::queue;
using std::priority_queue;
using std::vector;
using std::map;
using std::string;

const int N = 30;
const int target_num = 500;

int cnt;
vector<int> in;

void dfs(int now, int sum, int to) {
    if (sum == target_num && to == 10) {
        cnt ++;
        for (int i = 0; i < in.size(); i ++) cout << in[i] << ' ';
        cout << endl;
    }
    if (sum >= target_num || to >= 10) return;
    for (int i = now; i <= 73; i ++) {
        in.push_back(i);
        dfs(i, sum + i, to + 1);
        in.pop_back();
    }
}

int main() {
    freopen("all.txt", "w", stdout);
    dfs(44, 0, 0);
    cout << cnt << endl;
    return 0;
}

总共177376种，以下是部分方案