DFS + 减枝

1. 从高位开始枚举，满足总和小于n且因子的数量cnt < k进入递归
2. 递归的终点：总和 == n并且因子的数量cnt == k
3. 结果更新为因子数之和最大的方案

C++ 代码

#include <iostream>
#include <vector>
#include <cmath>
using  namespace std;

int n, k, p;
int v[21];

int resSum = -1;
vector<int> path, ans;

/* i:当前递归到的因子数，n:选取的因子数i^p的和(初始化为n，每一步减去v[i])，
   cnt:选取的因子数的个数，sum:选取的因子数之和 */
void DFS(int i, int n, int cnt, int sum) {
    if (n == 0 && cnt == k) {
        if (sum > resSum) {
            resSum = sum;
            ans = path;
        }
        return;
    }
    while (i > 0) {
        //减枝，防止递归爆栈
        if (n - v[i] >= 0 && cnt + 1 <= k) {
            path[cnt] = i;
            DFS(i, n - v[i], cnt + 1, sum + i);
        }
        i--;
    }
}

int main() {
    cin >> n >> k >> p;
    path.resize(k);
    int i = 0;
    while (pow(++i, p) <= n){
        //用数组存入i^p的值
        v[i] = pow(i, p);
    }
    i--;
    DFS(i, n, 0, 0);
    if (resSum == -1) puts("Impossible");
    else {
        printf("%d = %d^%d", n, ans[0], p);
        for (int i = 1; i < ans.size(); i++) {
            printf(" + %d^%d", ans[i], p);
        }
        cout << endl;
    }
    return 0;
}