377. Combination Sum IV

Here is the link.

I think that bottom up dynamic programming solution is best one to solve this algorithm. I need to warm up the algorithm using a simple example.

Case study [1, 2, 3] with target = 4

Let me work on example [1, 2, 3], given target = 4, how to solve the problem (The answer is 7)? l like quickly to go over each step and find the answer. I believe that will help me warm up dynamic programming solution bottom up, and master the algorithm.
number:
[1, 2, 3],
target = 4
all combinations:
(1,1,1,1)
(1,1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Observations

The order is important.

Two one, one two has three combinations; one is (1, 1, 2), another one is (1, 2, 1), and the third one is (2, 1, 1).
One one, one three has two combinations; one is (1, 3), another one is (3, 1).

First, given target = 4, let us declare dp (prefer a short name to explain) array with size 5, why? Since target has five values, 0, 1, 2, 3, 4.

Bottom up

Let us set dp[0] = 1, why? Because empty set is only option for value 0.
what is dp[1]?
We can exhaust all numbers in original array, which one can be added to set and then increase the value to 1, based on dp[0] = 1.
Only second element is value 1, so dp[1] = 1;
dp[2] has two options, element 2 with dp[0] or element 1 with dp[1], so dp[2] = 2;
dp[3] has three options, element 3 with dp[0] or element 2 with dp[1] or element 1 with dp[2], so dp[3] = dp[0] + dp[1] + dp[2] = 4;
dp[4] has three options, we only have 3 values, [1, 2,3], 4 is not in the array; Element 3 with dp[1] or element 2 with dp[2] or element 1 with dp[3], so dp[4] = dp[1] + dp[2] + dp[3] = 1 + 2 + 4 = 7.
In other words, I can write down those bottom up formulas in the following using F function:
F(0) = 1
F(1) = F(0)
F(2) = F(0) + F(1)
F(3) = F(0) + F(1) + F(2)
F(4) = F(1) + F(2) + F(3)

Top down

In other words, I can write down those bottom up formulas in the following using F function:
F(4) = F(1) + F(2) + F(3)
F(3) = F(0) + F(1) + F(2)
F(2) = F(0) + F(1)
F(1) = F(0)
F(0) = 1

I believe that the above exercise will help me to find pattern to apply dynamic programming using bottom up, and also I can quickly write a solution to match the example in the following.

Here are highlights:

1. Declare dynamic programming target array int[target + 1];
2. Set base value dp[0] = 1;
3. Go over target value i variable from 1 to target, bottom up, find all ways to form sum with value i, how to do the work?
4. Step 3, go over every element in the array, check if the element can be last one to be added, if it true, then subproblem with sum value is found.
5. Warm up the dynamic programming using simple example, shown my above analysis.

public class Solution {
    /// <summary>
        /// Leetcode 377 - combination sum 
        /// bottom up - dynamic programming 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int CombinationSum4(int[] nums, int target) {
            var combinations = new int[target + 1];

            combinations[0] = 1;

            // go over all options
            for (int i = 1; i < combinations.Length; i++)
            {
                for (int j = 0; j < nums.Length; j++)
                {
                    var number = i - nums[j];

                    if (number >= 0)
                    {
                        combinations[i] += combinations[number];
                    }
                }
            }

            return combinations[target];
        }        
}