连续邮资问题回溯法c++

连续邮资问题是一个经典的回溯法问题，可以使用C++语言实现。以下是一个基本的实现：

#include <iostream>
using namespace std;

const int MAXN = 10; // 邮票面值数量的最大值
const int MAXM = 100; // 邮资的最大值

int n; // 邮票面值数量
int a[MAXN]; // 邮票面值数组
bool ans[MAXM]; // 标记答案中的邮资是否存在
int exist[MAXM], cnt; // 存储存在的邮资和数量

// sum 表示当前邮资，k 表示当前枚举到第 k 张邮票
void dfs(int sum, int k) {
    if (k > n || sum >= MAXM) { // 枚举完所有邮票或邮资超过最大值
        return;
    }
    if (ans[sum]) { // 如果当前邮资已经存在，则跳过
        dfs(sum + a[k], k);
        return;
    }
    ans[sum] = true; // 将当前邮资标记为存在
    exist[cnt++] = sum; // 存储当前邮资
    dfs(sum + a[k], k); // 选择当前邮票
    dfs(sum, k + 1); // 不选择当前邮票
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dfs(0, 0); // 从邮资为 0 和第 0 张邮票开始枚举
    cout << "存在的邮资有：";
    for (int i = 0; i < cnt; i++) {
        cout << exist[i] << " ";
    }
    cout << endl;
    return 0;
}

该实现中使用了一个 `ans` 数组来标记答案中的邮资是否存在，同时使用了一个 `exist` 数组来存储存在的邮资和数量。在回溯过程中，如果当前邮资已经存在，则跳过；否则将当前邮资标记为存在，并存储当前邮资。最后输出存在的邮资即可。