Go - O(N * log N)
I don\'t think this one are medium complexity solutions. Hope nobody ask this during interview or just to 100% fail candidate.\nJust watch this video: https://w
I don\'t think this one are medium complexity solutions. Hope nobody ask this during interview or just to 100% fail candidate.\nJust watch this video: https://www.youtube.com/watch?v=xCsIkPLS4Ls\n\n```\nfunc numSubseq(nums []int, target int) int {\n\tconst MOD = 1000000007\n\texps := make([]int, len(nums))\n\tfor i:= range exps {\n\t\texps[i] = 1\n\t}\n\n\tfor i:=1; i < len(exps); i++ {\n\t\texps[i] = (2 * exps[i - 1]) % MOD\n\t}\n\n\tsort.Ints(nums)\n\tleft  := 0\n\tright := len(nums)-1\n\tcount := 0\n\n\tfor left <= right {\n\t\tif nums[left] + nums[right] > target {\n\t\t\tright--\n\t\t} else {\n\t\t\tcount = count + exps[right - left]\n\t\t\tleft++\n\t\t}\n\t}\n\n\treturn count % MOD\n}\n```\n\n**Unit Tests**\n```\nfunc Test_Number_of_Subsequences_That_Satisfy_the_Given_Sum_Condition(t *testing.T) {\n\ttestCases := []struct{\n\t\tnums []int\n\t\ttarget int\n\t\tresult int\n\t} {\n\t\t{ []int{3,5,6,7}, 9, 4,},\n\t\t{ []int{3,3,6,8}, 10, 6,},\n\t\t{ []int{2,3,3,4,6,7}, 12, 61,},\n\t\t{ []int{5,2,4,1,7,6,8}, 16, 127,},\n\t\t{ []int{14,4,6,6,20,8,5,6,8,12,6,10,14,9,17,16,9,7,14,11,14,15,13,11,10,18,13,17,17,14,17,7,9,5,10,13,8,5,18,20,7,5,5,15,19,14}, 22, 272187084,},\n\t}\n\n\tfor _, tc := range testCases {\n\t\tr := numSubseq(tc.nums, tc.target)\n\t\tif r != tc.result {\n\t\t\tt.Errorf("Source: %2d, target:%2d\\n Expected: %2d\\n Actual:   %2d\\n",\n\t\t\t\ttc.nums,\n\t\t\t\ttc.target,\n\t\t\t\ttc.result,\n\t\t\t\tr)\n\t\t}\n\t}\n}\n```
[]