target_sum_set_soln_2_py

n,target,k = 6, 10, 1
arr = [3,7, 1, 9, -1,5]

arr.sort()

# edge case with negative numbers therefore don't bisect
# arr = arr[:bisect_right(arr, target)] #array will not contain any number greater than target

answ_cnt = 0
def k_len_target_sum_subset(arr,target, subset_lst = []):
    global answ_cnt
    #print(subset_lst)
    subset_sum = sum(subset_lst)
    if target == subset_sum and len(subset_lst) == k:
        answ_cnt+=1
        print('ans',answ_cnt,subset_lst)
        return

    if target < subset_sum or len(subset_lst) > k:
        return False

    for idx,this_num in enumerate(arr):
        k_len_target_sum_subset(arr[idx+1:], target, subset_lst+[this_num]) #magical thing happening here take your time to understand this

k_len_target_sum_subset(arr,target)

if answ_cnt ==0:
    print('no solution')

'''
k =1
no solution

k = 2
ans 1 [1, 9]
ans 2 [3, 7]

k = 4
ans 1 [-1, 1, 3, 7]
'''