DP — Combinatorics Problem using Tabulation

What is a combinatorics problem?

Combinatorial problems involve finding a grouping, ordering, or assignment of a discrete, finite set of objects that satisfies given conditions.

Some common terminologies in combinatorics:

1. Candidate solutions: Candidate solutions are combinations of solution components that may be encountered during a solutions attempt but need not satisfy all given conditions.
2. Solutions: Solutions are candidate solutions that satisfy all given conditions.

Note

If you’re someone who is new to DP or need a quick revision, you can check out my blogs over here:

DP — Decision Problem using Tabulation

DP — Decision Problem using Memoization

Now, let’s take an example of a combinatorics problem and try solving it.

Here is the problem statement, given a target word and a word bank(array of words) we must return a possible combination of candidates where the chosen strings combine to form the target word. Given that, the same word may be chosen from the candidate set any number of times.

This is a visual representation of the problem, but the approach shown in the visual is a top-down dp approach

Intuition

Before jumping into the algorithm, let’s take some time to think about a possible solution to this problem. One way to approach this problem is that we can form combinations of all the words given in the word bank, and later check how many solutions we have constructed, among all the possible candidate solutions. This solution will surely work but won’t be an effective solution for real-world problems, as the time complexity is in the order of factorial.

So why don’t we think about this problem in terms of dynamic programming? We can view the posed problem as subproblems such that if a particular prefix is possible to construct then we’re worried only about finding a suffix that will go along with the prefix constructed which indeed helps us to construct the target word.

target word = “abcde”, if it is possible to construct “ab” then we’re focused on finding whether there is a word in word bank which could go along as a suffix to “ab” which will help us construct the target word, some possible suffixes are “cd” and “cde”; one important thing to note that is we can’t consider “de” as a possible suffix unless and unitl we can reach a prefix “abc”, as we have to maintain the original order of character occurrences in the target word

So, what is the prefix which will be available regardless of the words in the word bank? It is an empty string, which can be constructed without taking words from the word bank, so now we have our base case. Now, let’s try picking words from the word bank and check if it is the prefix of the target word, if so we keep track of this word. Now we in turn search for suffixes for the chosen word so that we can construct the given target word.

Algorithm

1. Initialize an array ‘dp’ of a list of strings that is of the size target word.
2. We check for base criteria that is whether there are words in the word bank which start with the same letter as the target word if so we add it to the list which is at the 0th index of our array.
3. Now we iterate over the array from 1st index to the end.
4. While iterating over the array, we check if the current prefix is already available in the word bank, if so we add it to the list of strings at the particular index.
5. We also check whether there are complimentary substrings that are available for this particular substring which we’re constructing currently, if so we once again add those combinations to the list of strings at the particular index.
6. We continue this process until we have checked for all possible substrings which also includes the target word.
7. In the end, now we return the possible combinations of strings that can be used to construct the target word.

Note

dp[i] contains a list of strings that are used to construct the substring consisting of characters from 0th index to ith index. So, when we’re at the 0th index we’re actually making the statement about the 1st character of the target word.

e.g:

target word = “purple”, word bank=[“purp”, “p”, “ur”, “le”, “purpl”]

dp[3] = [“purp, “p ur p”]

Simulation of the algorithm

target word = “purple”, word bank=[“purp”, “p”, “ur”, “le”, “purpl”]

step 1: Initially the dp array has the starting letter of the target word at the 0th index:

[[“p”], [], [], [], [], []]

step 2: Now we iterate from index 1 to the size of the target word in the dp array.

step 3: i = 1:

We check whether “pu” is available in the word bank, and the answer to it is no. So, now we check through all possible combinations of words(substrings from 0th index through i + 1 th index) and ultimately this doesn’t yield any combination either, so we end up with an empty list at 1th index.

step 4: i = 2:

We check whether “pur” is available in the word bank, and the answer to it is once again no. So, now we check through all combinations of words(substrings from 0th index through i + 1 th index) and this yields the combinations of prefix “p” and suffix “ur” from the word bank, so now we add this combination as a possibility to list of strings in this index.

dp[2] = [“p ur”]

step 5: i = 3:

We check whether “purp” is available in the word bank, and the answer to it is yes we do have it, so we add this as a possibility to the list of strings at this index. Now, we check through all combinations of words(substrings from 0th index through i + 1 th index) and this yields the combinations of the prefix “p ur” with suffix “p” from the word bank, so now we add this combination as a possibility to list of strings in this index.

dp[3] = [“purp”, “p ur p”]

step 6: i = 4:

We check whether “purpl” is available in the word bank, and the answer to it is yes we do have it, so we add this as a possibility to the list of strings at this index. Now, we check through all combinations of words(substrings from 0th index through i + 1 th index) and ultimately this doesn’t yield any combinations.

dp[4] = [“purpl”]

step 7: i = 5:

We check whether “purple” is available in the word bank, and the answer to it is no. Now, we check through all combinations of words(substrings from 0th index through i + 1 th index), and this yields the combinations of the prefix “p urp” with suffix “le” from the word bank, and prefix “p ur p” with suffix “le” form the word bank, so now we add this combination as a possibility to list of strings in this index.

dp[5] = [“purp le”, “p ur p le”]

Code

Note

Let’s quickly look at the basic steps involved in constructing a tabulation algorithm:

1. Visualize the problem as a table with proper dimensions suiting the inputs.
2. Initialize the table with the default values.
3. Fit the base case answers into the table.
4. Iterate through the table and fill the current position based on the results of the previous positions in the table.

Quick recap

1. We saw about ‘What is a combinatorics problem?’ and an example problem to go with it.
2. We saw about the intuition on how to solve this problem using dynamic programming.
3. Then we used tabulation to make the algorithm work efficiently.

What’s Next?

The problem which we discussed today can be found on leetcode, you could try solving it, using the tabulation approach which we have discussed:

Word Break II - LeetCode

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post with an optimization problem and how to solve the same using tabulation.

References

1. https://www.cs.ubc.ca/labs/algorithms/Courses/CPSC532D-05/Slides/ch1-slides.pdf