**Problem**

Given an array of positive integers `arr[]`

and a target `sum`

, find the number of permutations that form the sum using the elements of the array, with **repetition allowed**.

###### Dynamic Programming

We can solve this problem using dynamic programming. Let’s define `dp[i]`

as the number of permutations to form the sum `i`

. We initialize `dp[0] = 1`

because there’s only one way to form sum 0, which is using an empty array `{}`

.

**Optimal Substructure**

For each sum `i`

from 1 to the target `sum`

, we iterate through the array elements and add the number of permutations to form the sum: `i - arr[j]`

to `dp[i]`

. This way, we consider all possible combinations of elements to form the target sum.

dp[i] = dp[i - arr[0]] + dp[i - arr[1]] + ... + dp[i - arr[n-1]]

**Base case & Initialisation**

dp[0] = 1, number of permutations to make sum 0 is 1, using empty array dp[j] = 0, if j > 0

###### Pseudocode

```
countPermutations(arr, sum):
n = size of arr
dp[sum+1] = {0},
dp[0] = 1
for i from 1 to sum:
for j from 0 to n - 1:
if arr[j] <= i:
dp[i] += dp[i - arr[j]]
return dp[sum]
```

**Example**

Let `arr[] = {2, 3, 5}`

, and `sum = 5`

dp[0] = 1 ways to form sum 0: 1, using {} from i = 1 to sum: i = 1, from j = 0 to n-1: dp[1] = 0 ways to form sum 1: 0 i = 2, from j = 0 to n-1: dp[2] = dp[2 - arr[0]] = dp[2 - 2] = dp[0] = 1 ways to form sum 2: 1, using {2} Similarly, i = 3, from j = 0 to n-1: dp[3] = dp[3 - 2] + dp[3 - 3] = dp[1] + dp[0] = 1 + 0 = 1 ways to form sum 3: 1, using {3} i = 4, from j = 0 to n-1: dp[4] = dp[4 - 2] + dp[4 - 3] = dp[2] + dp[1] = 1 + 0 = 1 ways to form sum 4: 1, using {2, 2} i = 5, from j = 0 to n-1: dp[5] = dp[5 - 2] + dp[5 - 3] + dp[5 - 5] = dp[3] + dp[2] + dp[0] = 1 + 1 + 1 = 3 ways to form sum 5: 3, using {2, 3}, {3, 2}, {5}

Thus, number of ways (permutations) to form `sum 5`

using elements of `arr[] = {2, 3, 5}`

with repetition allowed is `3`

.

**Code Implementation**

```
//
// main.cpp
// Coin Change Permutation
//
// Created by Himanshu on 20/03/24.
//
#include <iostream>
#include <vector>
using namespace std;
int countPermutations(vector<int>& arr, int sum) {
int n = (int) arr.size();
vector<int> dp(sum + 1, 0);
// Base case: There is one way to form sum 0 using empty array
dp[0] = 1;
// Fill the dp table
for (int i = 1; i <= sum; i++) {
for (int j = 0; j < n; j++) {
// If the current element can be included in the sum
if (arr[j] <= i) {
dp[i] += dp[i - arr[j]];
}
}
}
// final result is stored in dp[sum]
return dp[sum];
}
int main() {
vector<int> arr = {2, 3, 5};
int sum = 5;
cout << "Number of permutations to form sum: "
<< sum << " is " << countPermutations(arr, sum) << endl;
return 0;
}
```

**Output**

Number of permutations to form sum: 5 is 3

**Time complexity:** **O(n * sum)**, n is the size of input array and sum is the target sum**Auxiliary Space:** **O(sum)**