c++ - 谁能告诉如何使用以下算法打印硬币找零问题中的所有可能组合？

Question

#include <bits/stdc++.h>

using namespace std;

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

ll int count(int s[], int m, int n)
{
  ll int t[m + 1][n + 1];
  for (int i = 0; i < m + 1; i++)
  {
    for (int j = 0; j < n + 1; j++)
    {
      if (i == 0)
        t[i][j] = 0;
      if (j == 0)
        t[i][j] = 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 if (s[i - 1] <= j)
      {
        t[i][j] = t[i - 1][j] + t[i][j - s[i - 1]];
        
      }
    }
  }

    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;
  std::cout << count(arr, m, n) << std::endl;

  return 0;
}

我需要使用上面的代码打印硬币找零问题中所有可能的组合。就像如果我们有一个数组 {1,2,3} 并且我们需要使用该数组总共 4 个，那么我们有四种可能的方法是：

{1,1,1,1},{1,1,2},{2,2},{1,3}

有没有办法使用上面的代码打印所有方式？谢谢

标签： c++dynamic-programming