Last active
June 29, 2018 23:21
-
-
Save adgarcia/ca03a56fb68c162a979f6c67c6e010b9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env stack | |
-- stack --resolver lts-6.15 script | |
{-# LANGUAGE OverloadedStrings #-} | |
-- import qualified Data.ByteString.Lazy.Char8 as L8 | |
-- targetSum -> currentSum -> subArray -> remainingNums -> subarray if it sums to targetSum OR [] otherwise | |
target_sum :: Integer -> Integer -> [Integer] -> [Integer] -> [Integer] | |
target_sum ts _ [] (n:ns) = target_sum ts n [n] ns {- our base case: there's nothing in the sub array -} | |
target_sum ts cs a _ {- yay! the current sum is the target sum! return the subarray -} | |
| ts == cs = a | |
target_sum ts cs (a:as) n {- the current sum is larger than the target sum. pop the first element and try again -} | |
| cs > ts = target_sum ts (cs-a) as n | |
target_sum ts cs (a:as) (n:ns) {- current sum less than target sum. increment sum and -} | |
| cs < ts = target_sum ts (cs+n) ((a:as)++[n]) ns | |
target_sum ts cs a [] {- ok so you didn't match anything and theres nothing left to check. better return an empty array-} | |
| cs /= ts = [] | |
main :: IO () | |
main = do | |
let my_sumTarget = 10 | |
let nums = [1, 4, 4, 4, 9, 4, 5, 1, 5] | |
-- let nums = [12] | |
print $ target_sum my_sumTarget 0 [] nums |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment