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)
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).
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)
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
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:
- Declare dynamic programming target array int[target + 1];
- Set base value dp[0] = 1;
- 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?
- 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.
- 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];
}
}
