Minimum Elements

The basic idea is to go over recursively to find the way such that the sum of chosen elements is ‘X’. For every element, we have two choices

1. Include the element in our set of chosen elements.

2. Don’t include the element in our set of chosen elements.

When we include an element in the set then we decrease the ‘X’ by the value of the element at the end. At any point, if we have X=0 then we can say that we have found the set of integers such that the sum of the set is equal to ‘X’.

Let us define a function “minimum( sum, num)”, where “sum” is the remaining sum that we have to make, “num” is the array that is given to us. Each time we have ‘n’ elements from which we have to take one.

If the function “minimum( sum, num)” returns INT_MAX which means that we cannot make the target sum ‘X’. 

Here is the algorithm:

• minimum function:
  • If sum is less than 0
    • return INT_MAX
  • If sum is 0
    • Return 0
  • Declare an integer variable “ans” and initialize it with INT_MAX.
  • Iterate over n(say ‘j’)
    • Update ans as ans=min(ans ,1+ minimum(sum-num[j],  num))
  • Return ans
• given function:
  • ans= numberOfWays( X, n, num).
  • If ans == INT_MAX
    • Return -1

                   Return ans

The basic idea is to store the results of the recursive calls to avoid repetition. We can memorize the results of our function calls in an array (say, ‘DP’).

So, let's first define dp[i]:

Dp[i] is the minimum number of elements that we need to make a sum equal to ‘i’.

Let us define a function “minimum( sum, num,dp)”, where “sum” is the remaining sum that we have to make, num is the array which is given to us and “dp” array is used to memorize the results. 

Here is the algorithm :

• minimum function:
  • If sum is less than 0
    • return INT_MAX
  • If sum is 0
    • Return 0
  • If dp[sum] != -1
    • Return dp[sum]
  • Declare an integer variable “ans” and initialize it with INT_MAX.
  • Iterate over n(say ‘j’)
    • Update ans as ans=min(ans ,1+ minimum(sum-num[j],  num, dp))
  • Update dp[sum] as ans.
  • Return ans.

• given function:
  • Declare an array “dp” of size ‘X’ + 1 and initialize it with -1.
  • ans= minimum( X, num, dp).
  • If ans == INT_MAX
    • Return -1

                   Return ans

The idea is similar to the previous approach. In this approach, we use an iterative way to store the minimum number of elements that are required to make the target sum ‘X’.

dp[i]= the minimum number of elements to make sum ‘i’.

If we already have calculated the minimum number of elements to make sum [0,1,..,i-1] then we can iterate over all the elements of the array and try to put an ith element of the array as the last element to make sum equal to ‘i’.

Here is the algorithm :

• Declare an integer variable ‘n’ and initialize it as the size of the array.
• Declare an array “dp” of size “X” + 1 and initialize it with INT_MAX.
• Set dp[0] = 0
• Run a loop from ‘i’ =1 to ‘i’ = X
  • Run another loop for iterating over all the elements of the array, say iterator ‘j’
    • If i-num[j] >= 0 && dp[i - num[j]] != INT_MAX
    • Update dp[i] as min(dp[i], 1+dp[i- num[j]])
• Return dp[X]