Coding Interview Problem

Question

Try solving this problem and prepare yourself for a coding interview round.

This problem was asked by Google.

Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null.

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since it sums up to 24.

Answer 1

https://code.sololearn.com/cWLGyFH7weto/?ref=app

Answer 2

here's my try, but the O(n) is 2^n, (n<=N)
N being total number of array elements

so i ll try to write better recursive solutions as well, ( sadly I am weak in recursion)

since all numbers are positive hence i have excluded array elements that are >= k , to keep working set small as possible.

I am generating all possible subsets, if want only the first then uncomment the break statement

https://code.sololearn.com/WLlQY42s9cWv/?ref=app

Answer 3

Mine, used recursion =)

https://code.sololearn.com/cCeJAP4I59lx/?ref=app

Answer 4

mine...

https://code.sololearn.com/cjtIVHtkAmOH/?ref=app

Answer 5

VcC if you can explain lamba. It will help others.

Answer 6

g=lambda x,y:f(x,y) equals
def g(x,y):
return(f(x,y))

It allows you to use a function without having to declare it. ex: max(a,key=lambda x:x*x-x+1) returns the maximum of array a using the criteria x*x-x+1 to compare elements. it is shorter thzn declaring f=xx-x+1 and then max(a,key=f)

Answer 7

yoohooo !