Count All Possible Sequence whose sum is K

[Question]: In an array count all possible sequence whose sum is K.
example:- [4,8,4] Target Sum = 8 So Output will be 2 because sequences are: [4,4] [8]

func printOneSeqSumK(ind: Int,
                     targetSum: Int,
                     currSum: inout Int,
                     inArray: [Int],
                     length: Int) -> Int {
    if ind == length {
        if  targetSum == currSum {
            return 1
        }
        return 0
    }
    
    currSum += inArray[ind]
    let left = printOneSeqSumK(ind: ind+1,
                    targetSum: targetSum,
                    currSum: &currSum,
                    inArray: inArray,
                       length: length)
    currSum -= inArray[ind]
    let right = printOneSeqSumK(ind: ind+1,
                    targetSum: targetSum,
                    currSum: &currSum,
                    inArray: inArray,
                       length: length)
    return left + right
}


let arrayInput = [4,8,4]
let length = arrayInput.count
let ind = 0
let targetSum = 8
var currSum = 0
let allPossibleSum = printOneSeqSumK(ind: ind,
                targetSum: targetSum,
                currSum: &currSum,
                inArray: arrayInput,
                length: length)
print(allPossibleSum)

Leave a Comment

Your email address will not be published. Required fields are marked *