Recursion

Recursion with Memoization

In order to emove the redundancy, we use memoization to store the results which have been calculated earlier.

Memoization is an easy method to track previously solved solutions. It can be used in both bottom up or top down methods.

[Medium] No.494 Target Sum

Approach1: Basic Recursion (Brute Force)

Time Complexity: O(2^N), where N is the number of nodes in the given list.

Space Complexity: O(N), the depth of recursion tree would be and need to have N times call stacks.

class Solution { public: int ans = 0; void helper(vector<int>& nums, int index, long target) { if(index == nums.size() && target == 0) { ans++; return; } if(index >= nums.size()) return; helper(nums, index + 1, target + nums[index]); helper(nums, index + 1, target - nums[index]); } int findTargetSumWays(vector<int>& nums, int S) { if(nums.size() == 0) return 0; helper(nums, 0, S); return ans; } };

Approach2: Recursion with Memoization

Time Complexity: O(l * N), where N is the number of element in the given list and l is the numbers of each element in the memo vector.

Space Complexity: O(l * N), the memo vector size.

class Solution { public: int helper(vector<int>& nums, int index, int sum, int S, vector<vector<int>>& memo) { if(index == nums.size()) { if(sum == S) return 1; else return 0; }else { //not visited if(memo[index][sum + 1000] == INT_MIN) { int add = helper(nums, index+1, sum + nums[index], S, memo); int sub = helper(nums, index+1, sum - nums[index], S, memo); memo[index][sum + 1000] = add + sub; } return memo[index][sum + 1000]; } } int findTargetSumWays(vector<int>& nums, int S) { if(nums.size() == 0) return 0; vector<vector<int>> memo(nums.size(), vector<int>(2001,INT_MIN)); return helper(nums, 0, 0, S, memo); } };