LeetCode Problem Solving: Remove Element and Combination Sum Techniques

This is my first article on my new blog. I have the habit of grinding DSA problems. I took a LeetCode assessment where I had to solve two problems: the Remove Element and Combination Sum problems. In this article, I will explain my thought process for solving each one.

Remove Element

this is the problem statement

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.

• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100

• 0 <= nums[i] <= 50

• 0 <= val <= 100

First, we need to define our constraints. We should remove the elements in place and are not allowed to create a new array. An easy solution is to use the built-in remove method in our programming language of choice. This will work since nums.length is just under 100 elements. However, if we scale it to 10^6, this approach will become very slow.

My solution is very simple: whenever you find an element equal to val, replace its value with another value from the rest of the array. If there are none left, stop and return the new length, which is our k. To achieve this, we will have a variable p whose job is to stay at the position of the last element that equals val. And that's it.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int p=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=val){
                nums[p]=nums[i];
                p++;
            }
        }
        return p;
    }
};

---

Combination Sum

this is the problem statement

,[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30

• 2 <= candidates[i] <= 40

• All elements of candidates are distinct.

• 1 <= target <= 40

After solving over 2000 problems on different platforms, I've gained some helpful insights. One of them is that when the constraints are very low, like in this problem, a brute-force solution will work just fine. That's exactly what I did for this problem.

When solving this problem, I divided it into two parts. First, I needed to generate the combinations. Second, I had to find a way to ensure the uniqueness of these combinations. The first part was easy—a recursive function with a loop to generate all possibilities.

For the second part, I had two ideas. The easiest was to sort each combination list and insert it into a set. This method guarantees uniqueness and is universal, working 100% of the time. However, if we read our constraints carefully, we see that all elements of candidates are distinct. So, I decided to set a starting point for the loop with each new recursive call. This was sufficient, and it's the role of the parameter i in the helper function.

class Solution {
public:
    void helper(int i,vector<int>& candidates,vector<int>& list,int target,vector<vector<int>>&ans){
        if(target==0){
            ans.push_back(list);
            return;
        }
        for(int j=i;j<candidates.size();j++){
            if(target-candidates[j]>=0){
                list.push_back(candidates[j]);
                helper(j,candidates,list,target-candidates[j],ans);
                list.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>>ans;
        vector<int>list;
        helper(0,candidates,list,target,ans);
        return ans;
    }
};

Thank you for reading my solutions. If you have any suggestions, please share them in the comments.