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)