# LEETCODE 1498. Number of Subsequences That Satisfy the Given Sum Condition 解题思路分析

```输入：nums = [3,5,6,7], target = 9

[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
```

```输入：nums = [3,3,6,8], target = 10

[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]```

```输入：nums = [2,3,3,4,6,7], target = 12

```

```输入：nums = [5,2,4,1,7,6,8], target = 16

• `1 <= nums.length <= 10^5`
• `1 <= nums[i] <= 10^6`
• `1 <= target <= 10^6`

[min]、[min,num1]、[min,num2]、[min,num1,num2,num3]、[min,num1,max]等等，这样的子数组有2^(n-1)个。（即[num1,num2,num3,num4,max]的全排列(2^(n-1))-1个，加上只有[min]的子数组，加起来共2^(n-1)个）

```long[] memo; // 记忆数组
public int numSubseq(int[] nums, int target) {
memo = new long[nums.length]; // 初始化记忆数组
Arrays.sort(nums); // 将数组排序
int left=0,right=nums.length-1; // 左右指针
long res=0; // 返回结果
while(left<=right){ // 循环每一个区间
// 如果区间内最大值与最小值之和大于target
if(nums[left]+nums[right]>target){
right--; // 向做移动右指针
}else{ // 合理区间
// 将区间内包含min的左右排列组合数累加至返回结果
res+=pow(right-left);
// 左区间向右移动一格
left++;
}
}
return (int)(res%1000000007);
}

long pow(int time){
if(time==0) return 1;
if(memo[time]>0) return memo[time];
long res=2*pow(time-1);
res%=1000000007;
memo[time]=res;
return res;
}```

Runtime: 33 ms, faster than 100.00% of Java online submissions for Number of Subsequences That Satisfy the Given Sum Condition.

Memory Usage: 59.7 MB, less than 100.00% of Java online submissions for Number of Subsequences That Satisfy the Given Sum Condition.