Combination Sum IV. Blind 75 question. Dynamic Programming

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

First just to understand this problem easily let's use more relatable example.

We'll use the concept of making change with coins.

Coin Change Example:

Imagine you're working at a school cafeteria, and you need to give change to students.

1. The Setup:
2. You have an unlimited supply of quarters (25¢), dimes (10¢), and nickels (5¢).
3. Your task is to find out how many different ways you can make change for various amounts.
4. The Challenge:
5. For each amount from 5¢ up to, say, 50¢, you want to know all the possible ways to make that change.
6. The order matters (giving a quarter then a nickel is considered different from giving a nickel then a quarter).
7. Solving the Problem: Let's work through this step-by-step:
8. 0¢: There's only 1 way to make no change (by giving no coins).
9. 5¢: 1 way (just a nickel)
10. 10¢: 2 ways (a dime, or two nickels)
11. 15¢: 4 ways (a dime + nickel, three nickels, nickel + dime, or quarter - nickel)
12. 20¢: 6 ways (...)
13. And so on...
14. The Thought Process: For each new amount, you think:
15. "If I give a nickel, how many ways were there to make the remaining amount?"
16. "If I give a dime, how many ways were there to make the remaining amount?"
17. "If I give a quarter, how many ways were there to make the remaining amount?"
18. Then you add up all these possibilities.

Building Up Knowledge:

• You start with simple amounts and work your way up.
• For each new amount, you use what you learned about smaller amounts.

The Programming Connection:

• In our code, the different coin values (5, 10, 25) are like our nums array.
• The amount we're making change for is our target.
• Our dp object is like a notebook where we write down how many ways there are to make each amount.

The Key Insight:

• To know how many ways there are to make 50¢, we don't start from scratch.
• We use our knowledge of how to make 45¢, 40¢, and 25¢ (by giving a nickel, dime, or quarter first).

Also, what are some real world application of combination sum?

1. Financial Planning and Investment Strategies:
2. Portfolio Optimisation: Determining the best combination of investments to maximise returns while minimising risk.
3. Retirement Planning: Calculating different ways to allocate savings over time to reach a retirement goal.
4. Resource Allocation in Business:
5. Project Scheduling: Finding the optimal way to allocate resources across different projects over time.
6. Manufacturing: Determining the most efficient way to cut materials to minimize waste (often called the "cutting stock problem").
7. Transportation and Logistics:
8. Route Planning: Finding the most efficient route for delivery vehicles, considering factors like distance, time, and capacity.
9. Airline Crew Scheduling: Optimising crew assignments to flights while adhering to regulations and minimising costs.

Let's see how we can solve it:

function combinationSumIvDraft(nums, target){
    const dp = new Array(target).fill(0)
    //only 1 way to pay 0$ 
    dp[0] = 1

    for(let amount = 1; amount <=target; amount++){
        dp[amount] = 0
        for(num of nums){
            if(num <= amount){
                dp[amount] += dp[amount - num]
            }
        }
    }

    return dp[target]
}

why? if(num < = amount) ?

if only current num is less than the amount, then we can use it to make our solution

For example, you can't use a quarter (25¢) to make 10¢.

why the logic  dp[amount] += dp[amount - num] ?

The number of ways to make 15¢ includes all the ways to make 5¢ (because we just used a 10¢ coin)

After submitting the solution to leetcode:

Complexities:

1. Time Complexity:
2. O(T * N), where T = target, N = length of input array nums
3. Space Complexity:
4. O(T), T is target