My journey in competitive programming

Today's Learning: Subsequences Patterns and Counting Subsequences with Sum K

Hello all!

Today, I dove deeper into subsequences, learning the different patterns and how to solve a more complicated problem involving sums. Here's what I worked on:

Learn All Patterns of Subsequences (Theory):

I first started to research the different types of subsequences. A subsequence is a sequence derived by removing some or no elements without changing the order of the elements. These are the basic patterns I researched:

Power Set: It is the set of all subsequences; the empty subsequence also is one of them.
Contiguous Subsequence: This subsequence is generated if elements from the original array are adjacent to each other.
Non-continuous Subsequence: This is a type where it is allowed to have spaces between the elements but with original order.

I learned how to apply recursion and backtracking for generating all possible subsequences. This technique really helps to explore all possible combinations.

Count All Subsequences with Sum K (Theory):

Next, I attempted even more powerful one: count all subsequences whose sum is a target K. My approach in this was to check for every subsequence and try out if the sum of the subsequence equaled to K. I wrote down by using recursion for making a build-up for the maximum possible subsequences so for each subsequence so long as it was made I am keeping track of its summation. If the summation turned into K, then I am considering this.

This problem taught me the importance of keeping a close eye on values, like sums, while examining subsequences and using recursion to solve it efficiently.