In this problem, we are asked the number of ways to achieve some value, $x$, using $n$ coins of distinct values where the order of coins does not matter. This is known as the "Unordered Coin Change" problem, which you can read about in CPH Chapter 7 under "Counting the Number of Solutions".

Main Idea

To solve this problem, let $\texttt{dp[w]}$ equal the number of ways to achieve the sum of values, $w$. Then, for some weight $w$, let's try to use each coin. For $\texttt{dp[w]}$, we'll transition from $\texttt{dp[w - coin[i]]}$ for all $i$, where $\texttt{coin[x]}$ defines the value of the $x$-th coin.

So, the transitions are:

Example Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first