1
#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;
}

i need to print all the combination possible in the coin change problem using the above code. like if we have an array {1,2,3} and we need to total of 4 using the array then we have Four Possible ways are:

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

is there a way to print all ways using the above code? Thanks

Alok Singh
  • 31
  • 6
  • Did you write this code yourself? – G. Sliepen Aug 29 '21 at 07:31
  • @G.Sliepen I watched some videos on dp and thought whether i can print all the possible combination. – Alok Singh Aug 29 '21 at 07:35
  • 1
    The problem with the above code is that the array `t` only stores the number of possible ways to get a given sum using the available coin values. You would need to modify it substantially to actually print out the possible combinations themselves. So the answer could be yes or no depending on what you meant with "using the above code". Note that the program you've written has very bad style: all one-letter variables, [bad coding challenge habits](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.). Consider rewriting it from scratch to do what you want. – G. Sliepen Aug 29 '21 at 07:48
  • @G.Sliepen Ok thanks for the tip. I will consider it – Alok Singh Aug 29 '21 at 07:50
  • 2
    Some interesting reading: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Lukas-T Aug 29 '21 at 07:53

0 Answers0