Find combination of numbers from list that add up to a sum in Haskell-CodePudding

I working on this programming problem:

Write a function 'howSum(targetSum, numbers)' that takes in a targetSum and an array of numbers as arguments. The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null. If there are multiple combinations possible, you may return any single one.

I solved a similar function that returns if it is possible:

canSum target nums
    | target>0 = any (\x -> canSum (target-x) nums) nums
    | target<0 = False
    | otherwise = True

canSum works by creating a recursive tree where the first call has the total sum and any creates a branch for each number with the remaining sum needed. If this reaches a target of 0, the branch to get there was a combination of subtracting numbers from nums meaning you can use numbers in the nums to sum to target.

But i can't seem to get a howSum function to work. How would that be written?

CodePudding user response：

You can modify the body of the function of canSum to create howSum'. For False you can return an empty list [], for True you return a list that contains one list (solution): the empty list; so:

howSum' :: (Num a, Ord a) => a -> [a] -> [[a]]
howSum' target nums
    | target > 0 = # …
    | target < 0 = []
    | otherwise = [[]]

For target > 0 we thus need to find candidate values. We thus will enumerate over the list, and thus make a recursive call. In case that returns a hit, we need to prepend that value to all the results of that call. We can use concatMap :: Foldable f => (a -> [b]) -> f a -> [b] to concatenate the results. This will thus look like:

howSum' :: (Num a, Ord a) => a -> [a] -> [[a]]
howSum' target nums
    | target > 0 = concatMap (\x -> … (howSum' (target-x) nums)) nums
    | target < 0 = []
    | otherwise = [[]]

where you still need to fill in the … part.

howSum' will thus list all possible ways to construct a result. You can use howSum' as a helper function to produce a single solution in case there is such solution.

This solution allows to use the same value in nums multiple times. It will also produce the same solution multiple times but in a different order, so [3, 5] and [5, 3] will both be solutions for 8. I leave it as an exercise to improve this further.