Number of ways to calculate a target number using only array elements - GeeksforGeeks
Given an integer array, find number of ways to calculate a target number using only array elements and addition or subtraction operator.
Read full article from Number of ways to calculate a target number using only array elements - GeeksforGeeks
Given an integer array, find number of ways to calculate a target number using only array elements and addition or subtraction operator.
The problem is similar to 0-1 Knapsack Problem where for every item, we either pick the complete item, or don’t pick it at all (0-1 property). The idea remains the same here i.e. we either include the current digit or ignore it. If we include the current digit, we subtract or add it from remaining target and recurse for remaining digits with new target. If target reaches 0, we increment the count. If we have processed all elements of the array and target is not reached, count remains unchanged.
Time Complexity of above solution is O(3^n) i.e. exponential.
int findTotalWays(vector<int> arr, int i, int k){ // If all elements are processed and // target is not reached, return 0 if (i >= arr.size() && k != 0) return 0; // If target is reached, return 1 if (k == 0) return 1; // Return total count of three cases // 1. Don't consider current element // 2. Consider current element and subtract it from target // 3. Consider current element and add it to target return findTotalWays(arr, i + 1, k) + findTotalWays(arr, i + 1, k - arr[i]) + findTotalWays(arr, i + 1, k + arr[i]);}