Today's Learning: Subsequence with Sum K, Combination Sum, and Combination Sum 2
Hey guys,
Today, I was solving some interesting problems related to subsequences and combination sums. Here is what I focused on:
1. Check if There Exists a Subsequence with Sum K:
I start with a problem where I am asked to check whether there exists any subsequence in an array which sums up to a given number K. The basic idea here was to explore all possible subsequences and check if their sum was equal to K. This I achieved with a recursive approach where I would consider every element in the array of whether I should include it in the current subsequence or skip it. In this way, I would look at all possible ways to find out if such a subsequence existed. It is an excellent practice on every decision step solving the problems using recursion.
2. Combination Sum:
This next problem is Combination Sum in which I was given to find all unique combinations of k numbers from a list, sums up to a given number. This problem requires the exploration of all possible combinations of the numbers and backtracking at every point when the sum got higher than the target number. I figured out how to include a recursive way that prevents duplicate combinations and ensures every combination is produced using elements of the list in non-decreasing order.
3. Combination Sum 2:
In the end, I also solved Combination Sum 2. That was almost identical to the first problem but with duplicates in the input array that should be handled. The problem was that it should not include duplicate combinations in the result. So, the same logic applied in the Combination Sum problem, but I had to add an extra step when skipping over duplicates in the recursion. It was a little more challenging this way, but it was also very rewarding once I got the idea.
Top comments (0)