# Solution For Number Of Subsequences That Satisfy The Given Sum Condition

Problem Statement:

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the elements of the subsequence is equal to target.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Solution:

To solve this problem, we can use the Two-Pointer algorithm. First, we sort the given array nums in non-decreasing order. Then, we initialize two pointers left and right.

We start with both the pointers at the beginning of the array. We move the right pointer to the end of the array while the sum of the elements between the left and right pointer is less than or equal to the target. Each time we move the right pointer, we calculate the number of subsequences that satisfy the given sum condition.

If the sum of the elements between left and right is greater than the target, we move the left pointer to the next index and repeat the above process until we reach the end of the array.

The number of subsequences that satisfy the given sum condition can be calculated as 2^(count) – 1, where count is the number of elements between left and right.

The base case for this algorithm is when the left pointer and the right pointer both point to the beginning of the array. In this case, we initialize the count variable to 1 and return it as the answer. This is because the empty subsequence is also counted as a valid subsequence.

Time Complexity:

The time complexity of this algorithm is O(nlogn) because we sort the given array before applying the Two-Pointer algorithm, which takes O(nlogn) time.

Space Complexity:

The space complexity of this algorithm is O(1) because we are not using any data structure to store intermediate values.

Code:

`class Solution:`

def numSubseq(self, nums: List[int], target: int) -> int:

nums.sort()

left, right = 0, len(nums) - 1

count = 0

while left <= right:

if nums[left] + nums[right] <= target:

count += 1 << (right - left)

left += 1

else:

right -= 1

return count % (10 ** 9 + 7)

Explanation:

In the above code, we have defined a function numSubseq that takes an array nums and an integer target as input.

First, we sort the array nums in non-decreasing order using the sort() function.

Next, we initialize two pointers left and right to the beginning and end of the array respectively. We also initialize a variable count to 0.

We then apply the Two-Pointer algorithm as explained above. If the sum of the elements between left and right is less than or equal to the target, we increment the count variable by 2^(right – left). We use the left shift operator to calculate the power of 2.

After applying the Two-Pointer algorithm, we return the count modulo 10^9 + 7 as the answer. This is because the answer can be very large and we need to return it modulo 10^9 + 7 as per the problem statement.

## Step by Step Implementation For Number Of Subsequences That Satisfy The Given Sum Condition

public int numSubseq(int[] nums, int target) { // sort the array Arrays.sort(nums); // initialize the answer int ans = 0; // compute the answer for (int i = 0; i < nums.length; i++) { int j = binarySearch(nums, target - nums[i]); if (j != -1) { ans += (1 << (j - i)); } } // return the answer return ans; } public int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; } else { right = mid - 1; } } return left - 1; }

def numSubseq(nums, target): # Initialize answer ans = 0 # Sort the array nums.sort() # Find number of subsequences # with sum less than equal # to target by including # and excluding every element for i in range(len(nums)): # If nums[i] > target, then # all further subsequences # will have sum more than target # so break the loop if (nums[i] > target): break # Find number of subsequences # with sum less than equal to # target by including nums[i] # If nums[j] > target-nums[i], # then all further j's will # have sum more than target # so no need to process further for j in range(i, len(nums)): if (nums[j] > target - nums[i]): break # Include nums[j] as part # of the solution ans += 1 << (j - i) # Remove nums[j] from # the solution ans -= 1 # Return the final answer return ans

var numSubseq = function(nums, target) { // sort the array in ascending order nums.sort((a, b) => a - b); // initialize two pointers, left and right let left = 0; let right = nums.length - 1; // initialize a count variable to keep track of the number of subsequnces that satisfy the given sum condition let count = 0; // iterate while left pointer is less than right pointer while (left < right) { // if the sum of the elements at the left and right pointers is less than the target sum, // this means we can increase the number of subsequnces by adding more elements from the left side // since the array is sorted in ascending order, all the elements to the right of the current left pointer will satisfy the sum condition if (nums[left] + nums[right] < target) { // since we can have any number of elements between left and right pointers that satisfy the sum condition, // we can increase the count by 2 ^ (right - left - 1) count += 2 ** (right - left - 1); // move the left pointer to the next element left++; } else { // move the right pointer to the next element right--; } } // return the count return count; };

int numSubseq(vector& nums, int target) { int res = 0, n = nums.size(), l = 0, r = n - 1; vector pows(n); pows[0] = 1; for (int i = 1; i < n; ++i) pows[i] = pows[i - 1] * 2 % MOD; sort(nums.begin(), nums.end()); while (l <= r) { if (nums[l] + nums[r] > target) { r--; } else { res = (res + pows[r - l]) % MOD; l++; } } return res; }

public int NumSubseq(int[] nums, int target) { // Sort the input array Array.Sort(nums); // Initialize an empty list Listlist = new List (); // Loop through each element in the array foreach(int num in nums) { // If the current element is less than the target, add it to the list if(num < target) { list.Add(num); } // If the current element is equal to the target, return 1 else if(num == target) { return 1; } // If the current element is greater than the target, break out of the loop else { break; } } // Initialize a counter variable int count = 0; // Loop through the list for(int i = 0; i < list.Count; i++) { // Initialize a sum variable int sum = list[i]; // Loop through the remaining elements in the list for(int j = i + 1; j < list.Count; j++) { // Add the next element in the list to the sum sum += list[j]; // If the sum is equal to the target, increment the counter if(sum == target) { count++; } // If the sum is greater than the target, break out of the loop else if(sum > target) { break; } } } // Return the count return count; }