Given an array arr[], consisting of N non-negative integers and an integer S, the task is to find the number of ways to obtain the sum S by adding or subtracting array elements.
Note: All the array elements need to be involved in generating the sum.
Examples:
Input: arr[] = {1, 1, 1, 1, 1}, S = 3
Output: 5
Explanation:
Following are the possible ways to obtain the sum S:
- -1 + 1 + 1 + 1 + 1 = 3
- 1 -1 + 1 + 1 + 1 = 3
- 1 + 1 – 1 + 1 + 1 = 3
- 1 + 1 + 1 – 1 + 1 = 3
- 1 + 1 + 1 + 1 – 1 = 3
Input: arr[] = {1, 2, 3, 4, 5}, S = 3
Output: 3
Explanation:
Following are the possible ways to obtain the sum S:
- -1 -2 -3 + 4 + 5 = 3
- -1 + 2 + 3 + 4 – 5 = 3
- 1 – 2 + 3 – 4 + 5 = 3
Recursive Approach: It can be observed that each array element can either be added or subtracted to obtain sum. Therefore, for each array element, recursively check for both the possibilities and increase count when sum S is obtained after reaching the end of the array.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include<bits/stdc++.h>using namespace std;// Function to count the number of waysint dfs(int nums[], int S, int curr_sum, int index, int n){ // Base Case: Reached the // end of the array if (index == n) { // Sum is equal to the // required sum if (S == curr_sum) return 1; else return 0; } // Recursively check if required sum // can be obtained by adding current // element or by subtracting the // current index element return dfs(nums, S, curr_sum + nums[index], index + 1, n) + dfs(nums, S, curr_sum - nums[index], index + 1, n);}// Function to call dfs() to // calculate the number of waysint findWays(int nums[], int S, int n){ return dfs(nums, S, 0, 0, n);}// Driver Codeint main(){ int S = 3; int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int answer = findWays(arr, S, n); cout << (answer); return 0;}// This code is contributed by chitranayal |
Java
// Java Program to implement// the above approachimport java.io.*;class GFG { // Function to call dfs() to // calculate the number of ways static int findWays(int[] nums, int S) { return dfs(nums, S, 0, 0); } // Function to count the number of ways static int dfs(int[] nums, int S, int curr_sum, int index) { // Base Case: Reached the // end of the array if (index == nums.length) { // Sum is equal to the // required sum if (S == curr_sum) return 1; else return 0; } // Recursively check if required sum // can be obtained by adding current // element or by subtracting the // current index element return dfs(nums, S, curr_sum + nums[index], index + 1) + dfs(nums, S, curr_sum - nums[index], index + 1); } // Driver Code public static void main(String[] args) { int S = 3; int[] arr = new int[] { 1, 2, 3, 4, 5 }; int answer = findWays(arr, S); System.out.println(answer); }} |
Python3
# Python3 program to implement# the above approach# Function to count the number of waysdef dfs(nums, S, curr_sum, index): # Base Case: Reached the # end of the array if (index == len(nums)): # Sum is equal to the # required sum if (S == curr_sum): return 1; else: return 0; # Recursively check if required sum # can be obtained by adding current # element or by subtracting the # current index element return (dfs(nums, S, curr_sum + nums[index], index + 1) + dfs(nums, S, curr_sum - nums[index], index + 1));# Function to call dfs() to# calculate the number of waysdef findWays(nums, S): return dfs(nums, S, 0, 0);# Driver Codeif __name__ == '__main__': S = 3; arr = [1, 2, 3, 4, 5]; answer = findWays(arr, S); print(answer);# This code is contributed by amal kumar choubey |
C#
// C# Program to implement// the above approachusing System;class GFG{// Function to call dfs() to // calculate the number of ways static int findWays(int[] nums, int S) { return dfs(nums, S, 0, 0); } // Function to count the number of ways static int dfs(int[] nums, int S, int curr_sum, int index) { // Base Case: Reached the // end of the array if (index == nums.Length) { // Sum is equal to the // required sum if (S == curr_sum) return 1; else return 0; } // Recursively check if required sum // can be obtained by adding current // element or by subtracting the // current index element return dfs(nums, S, curr_sum + nums[index], index + 1) + dfs(nums, S, curr_sum - nums[index], index + 1); } // Driver Code public static void Main(String[] args) { int S = 3; int[] arr = new int[] { 1, 2, 3, 4, 5 }; int answer = findWays(arr, S); Console.WriteLine(answer); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript Program to implement // the above approach // Function to call dfs() to // calculate the number of ways function findWays(nums, S) { return dfs(nums, S, 0, 0); } // Function to count the number of ways function dfs(nums, S, curr_sum, index) { // Base Case: Reached the // end of the array if (index == nums.length) { // Sum is equal to the // required sum if (S == curr_sum) return 1; else return 0; } // Recursively check if required sum // can be obtained by adding current // element or by subtracting the // current index element return dfs(nums, S, curr_sum + nums[index], index + 1) + dfs(nums, S, curr_sum - nums[index], index + 1); } let S = 3; let arr = [ 1, 2, 3, 4, 5 ]; let answer = findWays(arr, S); document.write(answer); </script> |
Output:
3
Time Complexity: O(2N)
Auxiliary Space: O(1)
Dynamic Programming Approach: The above recursive approach can be optimized by using Memoization.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to perform the DFS to calculate the// number of waysint dfs(vector<vector<int>> memo, int nums[], int S, int curr_sum, int index, int sum, int N){ // Base case: Reached the end of array if (index == N) { // If current sum is obtained if (S == curr_sum) return 1; // Otherwise else return 0; } // If previously calculated // subproblem occurred if (memo[index][curr_sum + sum] != INT_MIN) { return memo[index][curr_sum + sum]; } // Check if the required sum can // be obtained by adding current // element or by subtracting the // current index element int ans = dfs(memo, nums, index + 1, curr_sum + nums[index], S, sum, N) + dfs(memo, nums, index + 1, curr_sum - nums[index], S, sum, N); // Store the count of ways memo[index][curr_sum + sum] = ans; return ans;}// Function to call dfs// to calculate the number of waysint findWays(int nums[], int S, int N){ int sum = 0; // Iterate till the length of array for (int i = 0; i < N; i++) sum += nums[i]; // Initialize the memorization table vector<vector<int>> memo(N + 1, vector<int> (2 * sum + 1, INT_MIN)); return dfs(memo, nums, S, 0, 0, sum, N);}// Driver codeint main(){ int S = 3; int arr[] ={ 1, 2, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int answer = findWays(arr, S, N); cout << answer << endl; return 0;}// This code is contributed by divyesh072019 |
Java
// Java Program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to call dfs // to calculate the number of ways static int findWays(int[] nums, int S) { int sum = 0; // Iterate till the length of array for (int i = 0; i < nums.length; i++) sum += nums[i]; // Initialize the memorization table int[][] memo = new int[nums.length + 1][2 * sum + 1]; for (int[] m : memo) { Arrays.fill(m, Integer.MIN_VALUE); } return dfs(memo, nums, S, 0, 0, sum); } // Function to perform the DFS to calculate the // number of ways static int dfs(int[][] memo, int[] nums, int S, int curr_sum, int index, int sum) { // Base case: Reached the end of array if (index == nums.length) { // If current sum is obtained if (S == curr_sum) return 1; // Otherwise else return 0; } // If previously calculated // subproblem occurred if (memo[index][curr_sum + sum] != Integer.MIN_VALUE) { return memo[index][curr_sum + sum]; } // Check if the required sum can // be obtained by adding current // element or by subtracting the // current index element int ans = dfs(memo, nums, index + 1, curr_sum + nums[index], S, sum) + dfs(memo, nums, index + 1, curr_sum - nums[index], S, sum); // Store the count of ways memo[index][curr_sum + sum] = ans; return ans; } // Driver Code public static void main(String[] args) { int S = 3; int[] arr = new int[] { 1, 2, 3, 4, 5 }; int answer = findWays(arr, S); System.out.println(answer); }} |
Python3
# Python3 program to implement# the above approachimport sys# Function to call dfs to # calculate the number of waysdef findWays(nums, S): sum = 0 # Iterate till the length of array for i in range(len(nums)): sum += nums[i] # Initialize the memorization table memo = [[-sys.maxsize - 1 for i in range(2 * sum + 1)] for j in range(len(nums) + 1)] return dfs(memo, nums, S, 0, 0, sum)# Function to perform the DFS to calculate the# number of waysdef dfs(memo, nums, S, curr_sum, index, sum): # Base case: Reached the end of array if (index == len(nums)): # If current sum is obtained if (S == curr_sum): return 1 # Otherwise else: return 0 # If previously calculated # subproblem occurred if (memo[index][curr_sum + sum] != -sys.maxsize - 1): return memo[index][curr_sum + sum] # Check if the required sum can # be obtained by adding current # element or by subtracting the # current index element ans = (dfs(memo, nums, index + 1, curr_sum + nums[index], S, sum) + dfs(memo, nums, index + 1, curr_sum - nums[index], S, sum)) # Store the count of ways memo[index][curr_sum + sum] = ans return ans# Driver Codeif __name__ == '__main__': S = 3 arr = [ 1, 2, 3, 4, 5 ] answer = findWays(arr, S) print(answer)# This code is contributed by bgangwar59 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to call dfs// to calculate the number of waysstatic int findWays(int[] nums, int S){ int sum = 0; // Iterate till the length of array for(int i = 0; i < nums.Length; i++) sum += nums[i]; // Initialize the memorization table int[,] memo = new int[nums.Length + 1, 2 * sum + 1]; for(int i = 0; i < memo.GetLength(0); i++) { for(int j = 0; j < memo.GetLength(1); j++) { memo[i, j] = int.MinValue; } } return dfs(memo, nums, S, 0, 0, sum);}// Function to perform the DFS to calculate the// number of waysstatic int dfs(int[,] memo, int[] nums, int S, int curr_sum, int index, int sum){ // Base case: Reached the end of array if (index == nums.Length) { // If current sum is obtained if (S == curr_sum) return 1; // Otherwise else return 0; } // If previously calculated // subproblem occurred if (memo[index, curr_sum + sum] != int.MinValue) { return memo[index, curr_sum + sum]; } // Check if the required sum can // be obtained by adding current // element or by subtracting the // current index element int ans = dfs(memo, nums, index + 1, curr_sum + nums[index], S, sum) + dfs(memo, nums, index + 1, curr_sum - nums[index], S, sum); // Store the count of ways memo[index, curr_sum + sum] = ans; return ans;}// Driver Codepublic static void Main(String[] args){ int S = 3; int[] arr = new int[] { 1, 2, 3, 4, 5 }; int answer = findWays(arr, S); Console.WriteLine(answer);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to implement// the above approach// Function to call dfs// to calculate the number of waysfunction findWays(nums, S){ let sum = 0; // Iterate till the length of array for(let i = 0; i < nums.length; i++) sum += nums[i]; // Initialize the memorization table let memo = new Array([nums.length + 1][2 * sum + 1]); for(let i = 0; i < nums.length + 1; i++) { memo[i] = new Array(2 * sum + 1); for(let j = 0; j < 2 * sum + 1; j++) { memo[i][j] = Number.MIN_VALUE; } } return dfs(memo, nums, S, 0, 0, sum);}// Function to perform the DFS to calculate// the number of waysfunction dfs(memo, nums, S, curr_sum, index, sum){ // Base case: Reached the end of array if (index == nums.length) { // If current sum is obtained if (S == curr_sum) return 1; // Otherwise else return 0; } // If previously calculated // subproblem occurred if (memo[index][curr_sum + sum] != Number.MIN_VALUE) { return memo[index][curr_sum + sum]; } // Check if the required sum can // be obtained by adding current // element or by subtracting the // current index element let ans = dfs(memo, nums, index + 1, curr_sum + nums[index], S, sum) + dfs(memo, nums, index + 1, curr_sum - nums[index], S, sum); // Store the count of ways memo[index][curr_sum + sum] = ans; return ans;}// Driver Codelet S = 3;let arr = [ 1, 2, 3, 4, 5 ];let answer = findWays(arr, S);document.write(answer);// This code is contributed by avanitrachhadiya2155</script> |
Output:
3
Time Complexity: O(N * S)
Auxiliary Space: O(N * S)
Knapsack Approach: The idea is to implement the 0/1 Knapsack problem. Follow the steps below:
- The original problem reduces to finding the number of ways to find a subset of arr[] that are all positive and the remaining elements as negative, such that their sum is equal to S.
- Therefore, the problem is to finding no of subsets from the given array having sum (S + totalSum)/2.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to call dfs// to calculate the number of waysint knapSack(int nums[], int S, int n){ int sum = 0; for(int i = 0; i < n; i++) sum += nums[i]; // If target + sum is odd or // S exceeds sum if (sum < S || -sum > -S || (S + sum) % 2 == 1) // No sultion exists return 0; int dp[(S + sum) / 2 + 1]; for(int i = 0; i <= (S + sum) / 2; i++) dp[i] = 0; dp[0] = 1; for(int j = 0; j < n; j++) { for(int i = (S + sum) / 2; i >= nums[j]; i--) { dp[i] += dp[i - nums[j]]; } } // Return the answer return dp[(S + sum) / 2];}// Driver Codeint main(){ int S = 3; int arr[] = { 1, 2, 3, 4, 5 }; int answer = knapSack(arr, S, 5); cout << answer << endl;}// This code is contributed by amal kumar choubey |
Java
// Java Program to implement// the above approachimport java.io.*;class GFG { // Function to call dfs // to calculate the number of ways static int knapSack(int[] nums, int S) { int sum = 0; for (int i : nums) sum += i; // If target + sum is odd or S exceeds sum if (sum < S || -sum > -S || (S + sum) % 2 == 1) // No sultion exists return 0; int[] dp = new int[(S + sum) / 2 + 1]; dp[0] = 1; for (int num : nums) { for (int i = dp.length - 1; i >= num; i--) { dp[i] += dp[i - num]; } } // Return the answer return dp[dp.length - 1]; } // Driver Code public static void main(String[] args) { int S = 3; int[] arr = new int[] { 1, 2, 3, 4, 5 }; int answer = knapSack(arr, S); System.out.println(answer); }} |
Python3
# Python3 Program to implement# the above approach# Function to call dfs# to calculate the number of waysdef knapSack(nums, S): sum = 0; for i in range(len(nums)): sum += nums[i]; # If target + sum is odd or S exceeds sum if (sum < S or -sum > -S or (S + sum) % 2 == 1): # No sultion exists return 0; dp = [0]*(((S + sum) // 2) + 1); dp[0] = 1; for j in range(len(nums)): for i in range(len(dp) - 1, nums[j] - 1, -1): dp[i] += dp[i - nums[j]]; # Return the answer return dp[len(dp) - 1];# Driver Codeif __name__ == '__main__': S = 3; arr = [1, 2, 3, 4, 5 ]; answer = knapSack(arr, S); print(answer);# This code is contributed by Princi Singh |
C#
// C# Program to implement// the above approachusing System;class GFG{ // Function to call dfs // to calculate the number of ways static int knapSack(int[] nums, int S) { int sum = 0; foreach (int i in nums) sum += i; // If target + sum is odd or S exceeds sum if (sum < S || -sum > -S || (S + sum) % 2 == 1) // No sultion exists return 0; int[] dp = new int[(S + sum) / 2 + 1]; dp[0] = 1; foreach (int num in nums) { for (int i = dp.Length - 1; i >= num; i--) { dp[i] += dp[i - num]; } } // Return the answer return dp[dp.Length - 1]; } // Driver Code public static void Main(String[] args) { int S = 3; int[] arr = new int[] { 1, 2, 3, 4, 5 }; int answer = knapSack(arr, S); Console.WriteLine(answer); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript Program to implement // the above approach // Function to call dfs // to calculate the number of ways function knapSack(nums, S) { let sum = 0; for (let i = 0; i < nums.length; i++) sum += nums[i]; // If target + sum is odd or S exceeds sum if (sum < S || -sum > -S || (S + sum) % 2 == 1) // No sultion exists return 0; let dp = new Array(parseInt((S + sum) / 2, 10) + 1); dp.fill(0); dp[0] = 1; for (let num = 0; num < nums.length; num++) { for (let i = dp.length - 1; i >= nums[num]; i--) { dp[i] += dp[i - nums[num]]; } } // Return the answer return dp[dp.length - 1]; } let S = 3; let arr = [ 1, 2, 3, 4, 5 ]; let answer = knapSack(arr, S); document.write(answer);// This code is contributed by divyeshrabadiya07.</script> |
Output:
3
Time Complexity: O(n*(sum + S)), where sum denotes the sum of the array
Auxiliary Space: O(S + sum)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
