Java solution | Easy to understand |beats 100% | Beginner friendly
Intuition\n Describe your first thoughts on how to solve this problem. \nProblem requires finding the number of subsequences of the given array nums whose sum i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nProblem requires finding the number of subsequences of the given array nums whose sum is less than or equal to target. Sorting the array nums in non-decreasing order allows us to apply a two-pointer approach to count such subsequences efficiently. Specifically, we use two pointers l and r that point to the leftmost and rightmost elements of the sorted array, respectively. We then iterate while l is less than or equal to r and count the number of subsequences that can be formed with the first element pointed to by l and the last element pointed to by r. If the sum of these elements is less than or equal to target, then we can include all the subsequences that can be formed with these two elements and any element between them. We use a precomputed array p to calculate the number of subsequences that can be formed with a given range of indices.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Sort the given array nums in non-decreasing order.\n- Initialize two pointers l and r to the first and last elements of the sorted array, respectively.\n- Initialize a variable ans to 0 to store the number of subsequences whose sum is less than or equal to target.\n- Compute an array p such that p[i] stores 2^i modulo 1000000007.\n- Iterate while l is less than or equal to r.\n- If the sum of the elements pointed to by l and r is less than or equal to target, then we can include all the subsequences that can be formed with these two elements and any element between them. Add the number of such subsequences to ans. This number is given by p[r-l].\n- If the sum of the elements pointed to by l and r is greater than target, then decrement r. Otherwise, increment l.\n- Return ans modulo 1000000007.\n\n# Complexity\n- Time complexity:O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n    Arrays.sort(nums);\n    int l=0,r=nums.length,ans=0;\n    int [] p =new int[r];\n    p[0]=1;\n    for(int i=1;i<r;i++)p[i] = (p[i-1]*2)%1000000007;\n    r--;\n    while(l<=r){\n        if(nums[l]+nums[r]<=target){\n          ans+=p[r-l];\n          ans%=1000000007;\n          l++;\n        }\n        else\n        r--;\n    }\n    return ans;\n    }\n}\n```\nUpvotes are Encouraging
['Java']