Recursion it is : LeetCode 494

Today is 26 December, and I found a perfect problem that explains recursion to the point. LeetCode problem 494 is the POTD (Problem of the day). It is named Target Sum, but wait, not the normal generalized target sum that you are thinking right now. It is better to read the problem first and then proceed further here.

So, in this... better to follow your first intuition, that is handling addition (+) and subtraction (-), separately. And when it comes to handle cases individually and combining it in every step we have our BOSS ===> Recursion!

Everytime for each index you are adding and subtracting for each. And at the end when traversing the whole array then, just check if it is equal to the target value or not.

Well, here's the code below. But better you try it first.

*BTW, there is one more approach which I found later, just giving hint : an additional check of even totaling and playing with subsets and maximum value.... okay dp it is! 🫤

    void solve(int& ans, int ind, vector<int>& nums, int sum, int t) {
        if (ind == nums.size()) {
            if (sum == t) {
                ans++;
            }
            return;
        }
        solve(ans, ind + 1, nums, sum + nums[ind], t);
        solve(ans, ind + 1, nums, sum - nums[ind], t);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        int sum = 0;
        int ind = 0;
        solve(ans, ind, nums, sum, target);
        return ans;
    }