Combination Sum Leetcode Problem

This is a simple solution code and walkthrough of the leetcode problem combination sum

I have found that solutions to the combination sum problem are often very difficult to test. By this, I mean that walking through an example can be challenging due to the many recursive calls involved. To address this, I decided to create a walkthrough using a simple example. This solution combines both iteration and recursion, making the walkthrough process much easier to follow compared to solutions that rely on double recursion. Additionally, the example is short and simple enough for curious minds to easily follow and cement their understanding of the underlying functionality of the code. For this walkthrough, I have used the example of candidates = [2, 3, 4] and target = 6.

Below is an image of my handwritten walkthrough. I encourage you to review the solution and try to understand my reasoning for each step as presented in the image. The walkthrough progresses from left to right.

Maybe you can put the code on your laptop and the image of the walkthrough on your phone or tablet to better follow both code and walkthrough for the same example or other examples.

I find that:

An example with an array length of 3 is usually ideal.

A target value big enough for the elements in the array to easily make up the target is best for walkthrough purposes.

2.
Anything larger than an array length of 3 makes the process of walking through the code unnecessarily tedious, which defeats the purpose of the test.

The elements in the array must also be of a sizeable value. For example: Do not use candidates like [1, 3, 4] with a target of 6.

Here, the value 1 is very small, and including it unnecessarily increases the number of recursive calls.

For instance, we already know that a possible combination for a target of 6 is 1, 1, 1, 1, 1, 1. To find that particular solution, the code would make six recursive calls, and each of those 6 recursive calls will possibly lead to other recursive calls if the condition to find other combinations, after we meet the condition which found the combination [1, 1, 1, 1, 1, 1], and return, is not met. Now imagine doing the same for other combinations like [1, 1, 1, 3] and so on. It’s easy to see how this would quickly become exhausting.

In summary:

The condition for this test is:
The elements in the array must be of a sizeable value.
The target must be appropriate, not too small or too large.
Simply put, if you cannot handwrite the possible combinations of a target from your example candidate array to get your proposed target, then you should not use it to test.

After this, try and also see if you could do the same.

For now, I have decided to upload this version. If God permits, I will rewrite it in proper handwriting with a more polished and formatted presentation in the future.

Code: