<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def kSum ( self , A , k , target ) : <EOL> """<STR_LIT>""" <EOL> return self . dp ( A , k , target ) <EOL> def dp ( self , A , K , target ) : <EOL> """<STR_LIT>""" <EOL> n = len ( A ) <EOL> f = [ [ [ <NUM_LIT:0> for _ in xrange ( target + <NUM_LIT:1> ) ] for _ in xrange ( n + <NUM_LIT:1> ) ] for _ in xrange ( K + <NUM_LIT:1> ) ] <EOL> for ind , val in enumerate ( A ) : <EOL> if val <= target : <EOL> for j in xrange ( ind + <NUM_LIT:1> , n + <NUM_LIT:1> ) : <EOL> f [ <NUM_LIT:1> ] [ j ] [ val ] = <NUM_LIT:1> <EOL> for i in xrange ( <NUM_LIT:2> , K + <NUM_LIT:1> ) : <EOL> for j in xrange ( i , n + <NUM_LIT:1> ) : <EOL> for v in xrange ( <NUM_LIT:1> , target + <NUM_LIT:1> ) : <EOL> f [ i ] [ j ] [ v ] = <NUM_LIT:0> <EOL> if v - A [ j - <NUM_LIT:1> ] >= <NUM_LIT:0> : <EOL> f [ i ] [ j ] [ v ] += f [ i - <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] [ v - A [ j - <NUM_LIT:1> ] ] <EOL> if j - <NUM_LIT:1> >= i : <EOL> f [ i ] [ j ] [ v ] += f [ i ] [ j - <NUM_LIT:1> ] [ v ] <EOL> return f [ K ] [ n ] [ target ] <EOL> def dfs_TLE ( self , A , k , target , cur , ret ) : <EOL> if len ( cur ) == k and sum ( cur ) == target : <EOL> ret [ <NUM_LIT:0> ] += <NUM_LIT:1> <EOL> if not A or len ( cur ) >= k : <EOL> return <EOL> num = A . pop ( <NUM_LIT:0> ) <EOL> self . dfs_TLE ( A , k , target , cur , ret ) <EOL> A . push ( <NUM_LIT:0> , num ) <EOL> num = A . pop ( <NUM_LIT:0> ) <EOL> cur . append ( num ) <EOL> self . dfs_TLE ( A , k , target , cur , ret ) <EOL> cur . pop ( ) <EOL> A . push ( <NUM_LIT:0> , num ) <EOL> def dfs_TLE_2 ( self , A , k , target , s , l , la , ret ) : <EOL> """<STR_LIT>""" <EOL> if l == k and s == target : <EOL> ret [ <NUM_LIT:0> ] += <NUM_LIT:1> <EOL> if not A or l >= k or la + l < k : <EOL> return <EOL> num = A . pop ( <NUM_LIT:0> ) <EOL> self . dfs_TLE_2 ( A , k , target , s , l , la - <NUM_LIT:1> , ret ) <EOL> self . dfs_TLE_2 ( A , k , target , s + num , l + <NUM_LIT:1> , la - <NUM_LIT:1> , ret ) <EOL> A . push ( <NUM_LIT:0> , num ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> assert Solution ( ) . kSum ( [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:4> ] , <NUM_LIT:2> , <NUM_LIT:5> ) == <NUM_LIT:2> <EOL> assert Solution ( ) . kSum ( <EOL> [ <NUM_LIT:1> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> , <NUM_LIT:8> , <NUM_LIT:10> , <NUM_LIT:11> , <NUM_LIT:12> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:20> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:30> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <EOL> <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] , <NUM_LIT> , <NUM_LIT> ) == <NUM_LIT> </s>
