-1

My code is working for some scenarios, but it is not working for the following inputs

  • Target = 10
  • No of elements = 4
  • elements are = 2,3,3,4.

It returns no elements available. Could anyone please help here?

arr = []
target = int(input("Enter the target: "))
n = int(input("Enter the number of elements: "))

for i in range(n):
    arr.append(int(input()))

sorted_arr = sorted(arr)

selected = []
sum = 0
for num in sorted_arr:
    if sum+num <= target:
        sum += num
        selected.append(num)

su = 0
for nu in selected:
    su += nu
if su < target:
    selected.clear()

if len(selected) == 0:
    print("No elements available")
else:
    print(*selected)
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
Bala
  • 1
  • 1
  • It's because your algorithm 'greedily' consumes numbers while the sum < target. So for this example it will take 2 + 3 + 3 (= 8) and then reject the 4. Therefore it hasn't found a solution which sums to the target 10, so `if su < target: selected.clear()` will run and you get "No elements available". You instead need an algorithm which is able to try all combinations of numbers in the input array to find one that sums to the the target. – Anentropic Aug 08 '23 at 10:55
  • That is where am struggling. Could you please give some sample code? Thanks. – Bala Aug 08 '23 at 11:20
  • 1
    This page will help you. [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) – Nesi Aug 08 '23 at 11:38

1 Answers1

1

A solution to a similar question has been posted here.

In your case, after calling the subset_sum function, you can select the combinations with maximum amount of numbers:


target = 10
arr = [4,6,3,2,3,4]

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

combinations = list(subset_sum(arr,target))
max_numbers_combinations = [c for c in combinations if len(c) == max([len(comb) for comb in combinations])]
atteggiani
  • 94
  • 4