All Parenthesis 2 && Combination of Coins
After the first blog about how to understand recursive tree, I think we , at least , already had a little sense that we need to consider a recursion tree from 1.The height of the tree , 2. the branch factor of the tree. On this blog we will use another 2 question to hammer this process and explore more exciting parts about DFS recursion tree.
-- All Parenthesis 2
Get all valid permutations of l pairs of (), m pairs of [] and n pairs of {}.
Assumptions
- l, m, n >= 0
Examples
l = 1, m = 1, n = 0, all the valid permutations are ["()[]", "([])", "[()]", "[]()"]
-----------------------------------------------------------------------------------------------------------------------------
If you review the All parenthesis 1 in the previous blog post, you may come up quickly with a similarly solution ,which is we may carry out 6 parameters for each part of the 6 parenthesis. Besides, the rule to decide weather we can add certain parenthesis will be the same for the this one. However, It is actually more than what you think it might be :-)
If you keep that code above there will be 2 obvious defects. 1. It is not appropriate to carry out 7 or 8 parameters for any method, if we ever come to this situation, we need to come up with other solution around. 2.It has a flaw in its logic. Combination like " ( { ) [ } ] " will appear in the final result.
For fixed those 2 defects, we will use a array of integer to represent all number of parenthesis left and maintain a stack to manage the proper parenthesis combination.
Here is a solution code:
So what is this recursion tree will look like ?
1. The target length variable is equal to the height = 2 ( l + m + n)
2. The maximum branch factor will be 6, but the actually tree will never reach this point
-- > O( 6 ^ (2lmn) )
-- Combination of Coins
Given a number of different denominations of coins (e.g., 1 cent, 5 cents, 10 cents, 25 cents), get all the possible ways to pay a target number of cents.
Arguments
- coins - an array of positive integers representing the different denominations of coins, there are no duplicate numbers and the numbers are sorted by descending order, eg. {25, 10, 5, 2, 1}
- target - a non-negative integer representing the target number of cents, eg. 99
Assumptions
- coins is not null and is not empty, all the numbers in coins are positive
- target >= 0
- You have infinite number of coins for each of the denominations, you can pick any number of the coins.
Examples
coins = {2, 1}, target = 4, the return should be
[
[0, 4], (4 cents can be conducted by 0 * 2 cents + 4 * 1 cents)
[1, 2], (4 cents can be conducted by 1 * 2 cents + 2 * 1 cents)
[2, 0] (4 cents can be conducted by 2 * 2 cents + 0 * 1 cents)
]
--------------------------------------------------------------------------------------------------------------------
Let just take target = 99 cent, Coins = { 1 , 5 , 10 , 25 } as a example. How would you approach this problem ?
There is 2 approach that may solve this problem, and each of them have a different recursion tree.
Plan A:. The tree height = 99, for each level we will have 4 possible branches, which are take 1 ; 1 , 5 : 1 , 5 , 10 ; and take all of them. ( Note that we could add some code to optimal that once the total number of value we has already exceed than target value, we could then stop. )
Plan B: The tree height = 4, for each level we will have n possible branches, which depends on # of coins we can take for each value. For example if we consider value 25 cents in first level, we will have 4 branches, which are take 0 , 1 , 2 or 3 number of 25 cents in our final results. ( Same idea for the level of 10 we will have 10 branches and 100 for 1 cents)
What is your choose ? As a software engineer, we could analyze and compare this 2 plans in both time and space complexity.
Plan A : Time --> O( 4^99 ) , Space --> O(99)
Plan B : Time --> O( 99^4 ) , Space --> O( 4 )
After compare, it is not hard to find out that plan B is much better then plan A !
Here is the solution based on Plan B:
Here you go , building a recursion tree every time you write DFS code will help you better understand the internal working mechanism of you code and evaluate its performance easily !
Happy Coding < >
Ye Jiang
* Update( 7 / 22 / 2017 )
Here is another classic example that I want to add into this topic !
-- Binary Tree Sub-Path Sum to Target
Given a binary tree in which each node contains an integer number. Determine if there exists a path (the path can only be from one node to itself or to any of its descendants), the sum of the numbers on the path is the given target number.
Examples
5
/ \
2 11
/ \
6 14
/
3
If target = 17, There exists a path 11 + 6, the sum of the path is target.
If target = 20, There exists a path 11 + 6 + 3, the sum of the path is target.
If target = 10, There does not exist any paths sum of which is target.
If target = 11, There exists a path only containing the node 11.
-----------------------------------------------------------------------------------------------------------If we keep a actually path from root to current node and then check every possible subpath at each level we will end up with a O(n^2) solution, but for subpath sum we actually could do better :-)
Remember how to get range sum in constant time ?
-- We preprocessing the array to populate a prefix sum at each position, then the range sum from i - j is = prefixSum( j ) - prefixSum ( i - 1).
We could do a similar trick in this problem.
1. Use a set to store all previous prefix sum.
2. Keep a value to record total sum from root to current position
3. Then look for a possible sub-path sum by --> Set.contains( totalSum - target ) in O(1) time.
Here is a solution based on the strategy we come up with :
How is this recursive tree will look like ? ?
It will looks like exactly what the tree data structure itself ! 😎
and we will traverse this tree in a pre-order sequence.
So it is a deep first O(n) solution using call stack to simulate ^^
Hope you enjoyed 💫
Ye Jiang
No comments:
Post a Comment