# 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);

int ans = 0;

for (int i = 0; i < nums.length; i++) {
int j = binarySearch(nums, target - nums[i]);
if (j != -1) {
ans += (1 << (j - i));
}
}

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):

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 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
List list = 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)
{
}
// 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;
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]