Problem:
Coin Combination Problem II You have N coins each of which has a value a i .
Find the number of combinations that result when you choose K different coins in such a way that the total value of the coins is greater than or equal to L and less than or equal to R . Constraints  1 ≤ K ≤ N ≤ 40  1 ≤ a i ≤ 10 16  1 ≤ L ≤ R ≤ 10 16  All input values are given in integers  Input The input is given in the following format.  N  K  L  R  a 1  a 2 ... a N  Output Print the number of combinations in a line. Sample Input 1 2 2 1 9
5 1 Sample Output 1 1 Sample Input 2 5 2 7 19
3 5 4 2 2 Sample Output 2 5

Solution (Python):
import sys
import bisect


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = n//2
    ls = [[] for _ in range(m+1)]
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt].append(val)
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = 0
        val = 0
        for j in range(n-m):
            if i >> j & 1:
                cnt += 1
                val += a[m+j]
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = n//2
    ls = [[] for _ in range(m+1)]
    for i in range(1 << m):
        ls[bin(i).count("1")].append(sum([a[j] for j in range(m) if i >> j & 1]))
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = bin(i).count("1")
        val = sum([a[m+j] for j in range(n-m) if i >> j & 1])
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = n//2
    ls = [[0 for _ in range(combinations_count(m, i))] for i in range(m+1)]
    index = [0]*(m+1)
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt][index[cnt]] = val
        index[cnt] += 1
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = 0
        val = 0
        for j in range(n-m):
            if i >> j & 1:
                cnt += 1
                val += a[m+j]
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = (n+1)//2
    ls = [[] for _ in range(m+1)]
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt].append(val)
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = 0
        val = 0
        for j in range(n-m):
            if i >> j & 1:
                cnt += 1
                val += a[m+j]
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = n//2+1
    ls = [[] for _ in range(m+1)]
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt].append(val)
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = 0
        val = 0
        for j in range(n-m):
            if i >> j & 1:
                cnt += 1
                val += a[m+j]
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = (n-1)//2
    ls = [[] for _ in range(m+1)]
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt].append(val)
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = 0
        val = 0
        for j in range(n-m):
            if i >> j & 1:
                cnt += 1
                val += a[m+j]
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def largestRectangInHistgram(heights):
    stack = [-1]
    maxArea = 0

    for i in range(len(heights)):
        
        
        
        while stack[-1] != -1 and heights[stack[-1]] > heights[i]:
            lastElementIndex = stack.pop()
            maxArea = max(maxArea, heights[lastElementIndex] * (i - stack[-1] - 1))
        stack.append(i)

    
    
    while stack[-1] != -1:
        lastElementIndex = stack.pop()
        maxArea = max(maxArea, heights[lastElementIndex] * (len(heights) - stack[-1] - 1))

    return maxArea


def main():
    n, k, l, r = ns()
    a = na()

    pair1 = a[:n // 2]
    pair2 = a[n // 2:]
    ans = 0

    res1 = [[0, 0]]
    res2 = [[0, 0]]

    for p1 in pair1:
        tmp = [[cnt + 1, r + p1] for cnt, r in res1]
        res1 += tmp

    for p2 in pair2:
        tmp = [[cnt + 1, r + p2] for cnt, r in res2]
        res2 += tmp

    res2dic = {}
    for cnt, p2 in res2:
        if cnt not in res2dic.keys():
            res2dic[cnt] = [p2]
        else:
            res2dic[cnt].append(p2)
    for key in res2dic.keys():
        res2dic[key].sort()

    for cnt, r1 in res1:
        tmpk = k - cnt
        if tmpk < 0 or tmpk not in res2dic.keys():
            continue

        lnum = l - r1
        rnum = r - r1
        lidx = bisect.bisect_left(res2dic[tmpk], lnum)
        ridx = bisect.bisect_right(res2dic[tmpk], rnum)
        ans += ridx - lidx

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K, L, R = LI()
    a = LI()

    N_half_A = N // 2
    A_sum = [[] for _ in range(N_half_A + 1)]
    for i in range(2 ** N_half_A):
        sum = 0
        num = 0
        for j in range(N_half_A):
            if (i >> j) & 1:
                sum += a[j]
                num += 1
        A_sum[num].append(sum)

    N_half_B = N - N_half_A
    B_sum = [[] for _ in range(N_half_B + 1)]
    for i in range(2 ** N_half_B):
        sum = 0
        num = 0
        for j in range(N_half_B):
            if (i >> j) & 1:
                sum += a[N_half_A + j]
                num += 1
        B_sum[num].append(sum)
    for i in B_sum:
        i.sort()

    ans = 0
    for i in range(N_half_A + 1):
        if 0 <= K - i <= N_half_B:
            for j in A_sum[i]:
                idx_l = bisect.bisect_left(B_sum[K-i], L - j)
                idx_r = bisect.bisect_right(B_sum[K-i], R - j)
                ans += idx_r - idx_l

    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):

from bisect import bisect, bisect_left
N, K, L, R = map(int, input().split())
*A, = map(int, input().split())


def enum(A):
    n = len(A)
    ret = [[] for _ in [0]*(N+1)]
    for i in range(1 << n):
        sun = 0
        cnt = 0
        for j, a in enumerate(A):
            if i >> j & 1:
                sun += a
                cnt += 1
        ret[cnt].append(sun)

    return [sorted(r) for r in ret]


S1 = enum(A[:N//2])
S2 = enum(A[N//2:])

ans = 0
for k, _S1 in enumerate(S1):
    if k == K:
        l = bisect_left(_S1, L)
        r = bisect(_S1, R)
        ans += r-l
        continue
    if K-k < 0:
        break

    _S2 = S2[K-k]
    for a in _S1:
        l = bisect_left(_S2, L-a)
        r = bisect(_S2, R-a)
        ans += r-l

print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k,l,r = LI()
    a = LI()
    n1 = n>>1
    n2 = n-n1
    s1 = [[] for i in range(n1+1)]
    s2 = [[] for i in range(n2+1)]
    for b in range(1<<n1):
        s = 0
        j = 0
        for i in range(n1):
            if not b&(1<<i):
                continue
            s += a[i]
            j += 1
        s1[j].append(s)

    for b in range(1<<n2):
        s = 0
        j = 0
        for i in range(n2):
            if not b&(1<<i):
                continue
            s += a[i+n1]
            j += 1
        s2[j].append(s)
    for i in range(n2+1):
        s2[i].sort()
    ans = 0
    for i in range(n1+1):
        if i > k:
            break
        j = k-i
        if j > n2:
            continue
        for s in s1[i]:
            a,b = bisect.bisect_left(s2[j],l-s),bisect.bisect_right(s2[j],r-s)
            ans += b-a
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):


from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, K, L, R = iim()
    A = list(iim())

    n2 = N // 2

    def calc(a, b):
        d0 = [[] for i in range(K)]
        for i in range(a, b):
            x = A[i]
            for k in range(K-1, 0, -1):
                d1 = d0[k-1]
                d2 = d0[k]
                for v1 in d1:
                    v1 += x
                    if v1 > R: continue
                    d2.append(v1)
            d0[0].append(x)
        return d0

    da = calc(0, n2)
    db = calc(n2, N)

    for i in range(K-1):
        
        db[i].sort()

    ans = 0
    for k in range(1, K):
        j = K-k-1
        d1 = da[k-1]
        d2 = db[j]

        pos1 = 0
        for k1 in d1:
            
            pos1 = bisect_left(d2, L-k1)
            pos2 = bisect_left(d2, R+1-k1, pos1)
            

            ans += pos2 - pos1

    for dx in [da[-1], db[-1]]:
        for val in dx:
            if L <= val <= R:
                ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
from bisect import bisect_left, bisect_right
from itertools import combinations


if __name__ == "__main__":
    N, K, L, R = map(lambda x: int(x), input().split())
    coins = list(map(lambda x: int(x), input().split()))

    N_half = N // 2
    c1 = [list(map(sum, combinations(coins[:N_half], i))) for i in range(0, N_half + 1)]
    c2 = [list(map(sum, combinations(coins[N_half:], i)))
          for i in range(0, N - N_half + 1)]
    for i in range(0, N - N_half + 1):
        c2[i].sort()

    ans = 0
    for i in range(0, K + 1):
        if K - i < 0 or K - i > N - N_half or i > N_half:
            continue
        for a in c1[i]:
            low = bisect_left(c2[K - i], L - a)  
            high = bisect_right(c2[K - i], R - a)  
            ans += high - low

    print(ans)

Solution (Python):
import bisect 
from itertools import combinations

coins = []
line = input()
n, k, l, r = list(map(int, line.split()))
line = input()
coins = list(map(int, line.split()))

def solve():
    n2 = n // 2
    c1 = [ list(map(sum, combinations(coins[:n2], z))) for z in range(0, n2 + 1) ]
    c2 = [ list(map(sum, combinations(coins[n2:], z))) for z in range(0, n - n2 + 1) ]
    for i in range(0, n - n2 + 1):
        c2[i].sort()
    ans = 0
    for i in range(0, k + 1):
        if k - i < 0 or k - i > n - n2 or i > n2:
            continue
        for a in c1[i]:
            low = bisect.bisect_left(c2[k - i], l - a)
            high = bisect.bisect_right(c2[k - i], r - a)
            ans += high - low
    return ans

print(solve())

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br

def makeItems(lst, size):
    length = len(lst)
    ret = [[] for _ in range(size + 2)]
    ret[0] = [0]
    for a in lst:
        for b in range(size, -1, -1):
            add = [a + c for c in ret[b]]
            ret[b + 1].extend(add)
    return ret


def main():
    n, k, l, r = map(int, input().split())
    aList = list(map(int, input().split()))
    aLeft = aList[:n // 2]
    aRight = aList[n // 2:]
    leftItems = makeItems(aLeft, k)
    rightItems = makeItems(aRight, k)
    
    for lst in rightItems:
        lst.sort()
    
    ans = 0
    for i, lst in enumerate(leftItems):
        if i > k:continue
        for item in lst:
            minLimit = l - item
            maxLimit = r - item
            left = bl(rightItems[k - i], minLimit)
            right = br(rightItems[k - i], maxLimit)
            ans += right - left
    
    print(ans)

main()

Solution (Python):
from itertools import combinations
from collections import Counter
N, K, L, R, *A = map(int, open(0).read().split())
def make(A, K):
    return [Counter(map(sum, combinations(A, l))) for l in range(0, K+1)]

P = make(A[:N//2], K)
Q = make(A[N//2:], K)

ans = 0
for i in range(K+1):
    p = P[i]; q = Q[K-i]
    sq = sorted(q)
    l = r = len(q)
    s = 0
    for k, v in sorted(p.items()):
        while r and k+sq[r-1] > R:
            r -= 1
            s -= q[sq[r]]
        while l and k+sq[l-1] >= L:
            l -= 1
            s += q[sq[l]]
        ans += v * s
print(ans)