Haskell function that displays all the combinations in the input list that are added to the input number

Question

I want to write a function in haskell that takes a list of integers and an integer value as input and displays a list of all lists containing combinations of elements that add to the input integer.

For example:

myFunc [3,7,5,9,13,17] 30 = [[13,17], [3,5,9,13]]

Attempt:

myFunc :: [Integer] -> Integer -> [[Integer]] myFunc list sm = case list of [] -> [] [x] | x == sm -> [x] | otherwise -> [] (x : xs) | x + myFunc xs == sm -> [x] ++ myFunc[xs] | otherwise -> myFunc xs 

My code produces only one combination, and this combination should be consistent, which I do not want to achieve

Answer 1

Write a function to create all subsets

 f [] = [[]] f (x:xs) = f xs ++ map (x:) (f xs) 

then use the filter

 filter ((==30) . sum) $ f [3,7,5,9,13,17] [[13,17],[3,5,9,13]] 

as suggested by @Ingo, you can crop the list at the time of its creation, for example

 f :: (Num a, Ord a) => [a] -> [[a]] f [] = [[]] f (x:xs) = f xs ++ (filter ((<=30) . sum) $ map (x:) $ f xs) 

should work faster than generating all 2 ^ N elements.

Answer 2

An alternative could be to use the right fold:

 fun :: (Foldable t, Num a, Eq a) => ta -> a -> [[a]] fun = foldr go $ \a -> if a == 0 then [[]] else [] where go xfa = fa ++ ((x:) <$> f (a - x)) 

then

 \> fun [3,7,5,9,13,17] 30 [[13,17],[3,5,9,13]] \> fun [3,7,5,9,13,17] 12 [[7,5],[3,9]] 

The advantage of this approach is that it does not create any lists if it does not add to the desired value. Whereas the filtration-based approach will create all possible lists of subsequences in order to remove most of them during the filtering phase.

Answer 3

You can use subsequences from Data.List to give you any possible combination of values ​​and then filter based on your requirement, which they add to 30.

 myFunc :: [Integer] -> Integer -> [[Integer]] myFunc list sm = filter (\x -> sum x == sm) $ subsequences list 

Answer 4

Here is an alternative solution idea: Create a list of lists that are summed with the target number, that is:

 [30] [29,1] [28,2] [28,1,1] ... 

and only then filter those that can be created from your list.

Pro: it can be much faster, especially if your input list is long and your target number is relatively small, so the list of list items is much smaller than the list of subsets of your input list.

Con: only works when 0 is not in the game.

Finally, you can do this in both directions and write a function that decides which algorthm will be faster, given some input list and target number.