DEV Community

Cover image for Recursion it is : LeetCode 494
Ankit Rattan
Ankit Rattan

Posted on

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;
    }
Enter fullscreen mode Exit fullscreen mode

Image of Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay