Given a integer array, and a number n. Return true if n can be consisted by a subset of array.
For example, arr[]={3, 2, 3, 5}, n=11, return true; arr[]={3, 2, 3, 5}, n=12, return false
This problem can be solved by HashSet. Loop element i in arr[]. For each loop, get the value of sum i and each element in hashset. And put the value in hashset again. And put element i in hashset at the end of loop.
Check my code on github: link
Given a dictionary, and a string, find is string can be broke down by words in dictionary.
For example, dict = [cat, cats, and, dog, sand], str=’catsanddog’
Should return ‘cat sand dog’, ‘cats and dog’
Naive way is from-top-to-bottom.
For example, if we want to check [c1, c2, c3, c4, c5] is breakable, we check c[1,…,j] and c[j+1,…,5] where j=1, 2, 3, 4
Another way is from-bottom-to-top:
Check if [c1], [c2], [c3], [c4], [c5] are breakable.
Check if [c1, c2], [c2, c3], [c3, c4], [c4, c5] are breakable.
Check if [c1, c2, c3], [c2, c3, c4], [c3, c4, c5] are breakable.
Check if [c1, c2, c3, c4], [c2, c3, c4, c5] are breakable.
Finally, check if [c1, c2, c3, c4, c5] is breakable.
A better way is similar to minimum coin problem. link
Use an auxiliary array breakable[]. breakable[i] indicates if [c1,…,ci] is breakable.
Set a pointer moving from left to right, the process is like below:
Based on that, my code print all the possible breakdown options. Check here: link