# Finding Permutations that Form the Sum | Coin Change Permutation

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)