如何基于给定动态规划硬币找零C++代码打印所有可行组合？

实现思路 #

原代码已经构建好了统计组合数的二维DP表t，其中t[i][j]代表用前i种硬币凑出金额j的组合数。我们只需基于这张DP表进行回溯，即可得到所有不重复的有效组合：

• 从坐标(m, n)（用全部硬币凑目标金额的最终状态）开始倒推
• 每次可选两个分支：
  • 不选第i种硬币：直接跳转到(i-1, j)状态，仅当t[i-1][j] > 0时该路径存在有效组合
  • 选第i种硬币：跳转到(i, j - s[i-1])状态，同时将s[i-1]加入当前路径，仅当s[i-1] <= j且t[i][j - s[i-1]] > 0时该路径有效
• 当j == 0时说明已经凑出目标金额，输出当前路径即可
  由于是按硬币顺序遍历选择，最终输出的组合天然无重复排列，符合常规组合输出要求

修改后完整代码 #

#include <bits/stdc++.h>

using namespace std;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ll long long
#define mod 1000000007

// 回溯函数：根据DP表输出所有组合
void backtrack(int i, int j, int s[], vector<vector<ll>>& t, vector<int>& path) {
    if (j == 0) {
        // 输出组合，路径反向后为非降序排列
        cout << "{";
        for (int k = path.size() - 1; k >= 0; k--) {
            if (k != path.size() - 1) cout << ",";
            cout << path[k];
        }
        cout << "}\n";
        return;
    }
    if (i == 0) return;

    // 先走不选当前硬币的分支，保证输出顺序和示例一致
    if (t[i-1][j] > 0) {
        backtrack(i-1, j, s, t, path);
    }

    // 再走选当前硬币的分支
    if (s[i-1] <= j && t[i][j - s[i-1]] > 0) {
        path.push_back(s[i-1]);
        backtrack(i, j - s[i-1], s, t, path);
        path.pop_back();
    }
}

ll count(int s[], int m, int n)
{
    // 替换可变长度数组为标准vector，兼容性更好
    vector<vector<ll>> t(m + 1, vector<ll>(n + 1, 0));
    for (int i = 0; i < m + 1; i++)
    {
        t[i][0] = 1;
    }
    for (int i = 1; i < m + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            if (s[i - 1] > j)
                t[i][j] = t[i - 1][j];
            else
                t[i][j] = t[i - 1][j] + t[i][j - s[i - 1]];
        }
    }

    // 统计完DP表后调用回溯输出所有组合
    vector<int> path;
    cout << "所有有效组合：\n";
    backtrack(m, n, s, t, path);
    return t[m][n];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif //

    int arr[] = {1, 2, 3};
    int m = 3, n = 4;
    ll total = count(arr, m, n);
    cout << "\n组合总数量：" << total << endl;

    return 0;
}

运行输出示例 #

所有有效组合：
{1,1,1,1}
{1,1,2}
{2,2}
{1,3}

组合总数量：4

内容的提问来源于stack exchange，提问作者Alok Singh