2

I have the following piece of code which finds whether any 4 combination in the list sums up to a value(say 7) is possible.If possible it prints 1 else 0. it takes the:- number of list element(n) , list(test) and the number which needs to be checked(say 7)(x here).

Every time I execute it on any online platform it shows "Time limit exceeded". How I can optimize it below 0.87s??Provided I have used "itertools" here.Where I am doing it wrong.

import itertools
t=int(input())
while t!=0:
    n=int(input())
    test=[int(val) for val in input().strip().split()]
    x=int(input())
    generator=(itertools.combinations(test,4))
    for elem in generator:
        val=elem
        if sum(val)==x:
            flag=1
            break
            break
    if not flag:
        print('0')
    else:
        print('1')
    t=t-1
user10418143
  • 220
  • 3
  • 11
  • Rather than maually looping through values, have you looked into `any()` or `all()`? – G. Anderson Mar 01 '19 at 20:21
  • Where is `n` used in this code? – roganjosh Mar 01 '19 at 20:24
  • And why does `test` need to be computed on every iteration? – roganjosh Mar 01 '19 at 20:27
  • 1
    What are some of the lists and values you're testing with? I think you should separate your inputs from your processing, so first get input for t, then secondly keep looping for inputs until the user sends 'q' ( or something), and then pass both t and list to your logic. – Tony Mar 01 '19 at 20:40
  • Are the numbers always positive? If so, you should not use `itertools.combinations` since it unnecessarily generates all possible combinations. You should write your own generator that short-circuits the search when the 3 or less numbers you have already reaches 7. – blhsing Mar 01 '19 at 20:40
  • How to build my own generator in this case can u give a hint? – user10418143 Mar 02 '19 at 03:05

0 Answers0