My Python program solved this problem using 0.7+ seconds and 64000+KB memory. However, I saw some people solved it with Python using just about 0.1 secs and 500KB mem. Can anyone give me a hint about how to reach that efficiency?

Try to use bitmasks instead of using recursion;)

thx!!

You can solve this task with (n/2) * 2^(n/2) complexity using meet in the middle