title: How to check if a sum is possible in array?
body: <blockquote>
    <p>Given an array of <strong>N</strong> integers, check if it is possible to obtain a sum of <strong>S</strong>, by choosing some (or none) elements of the array and adding them. </p>
  </blockquote>
  
  <p>I tried solving this using a greedy approach by first sorting the array and then approaching closer and closer to the sum. However it does not work.</p>
  
  <p>Can anyone please tell me how should I approach this problem?</p>
  
  <pre><code>t = int(input())
  for foo in range(t):
      n = int(input())
      arr = list(map(int, input().split()))
      s = int(input())
      sum = 0
  
      for a in range(len(arr)):
          for b in range(len(arr)-a-1):
              if(arr[b] &gt; arr[b+1]):
                  temp = arr[b]
                  arr[b] = arr[b+1]
                  arr[b+1] = temp
  
      for i in arr:
          if((sum + i) &lt;= s):
              sum += i
  
      if(sum == s):
          print("YES")
      else:
          print("NO")
  </code></pre>