Problem Sub array sums to target - RobAllan27/CodingProblems GitHub Wiki

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.

Solution I will sort this in descending order. Then I will use a recursive algorithm - take the first digt and see if the ramain elements in the array if I can make the target minus the left most digit.

Further optimisation, if I have a repeating integer after then I know that cannot be part of a sub array, so I can can that loop. for example 8,8,2,3 when I have done the first 8, and tried the permutations, then I can ignore the 2nd 8 and delete it.

Test case [12, 1, 12, 3, 1] 24 return 12, 12 [12, 1, 12, 3, 1] 15 return 12, 3 [12, 1, 8, 3, 1] 20 return 12, 3, 1,1 [1, 2, 3, 4, 5] 15 return 5,4,3,2,1 [1] 1 return 1 [2,2] 5 return null [3,3,3,4,4,4,5,5,5,] 12 return 5,4,3,