How to Find all subsequences with sum equals to K

[Question] : In a given array find all possible sequence whose sum is certain number:
For example:- [4,8,4] Target Sum = 8 So Output will be [4,4] [8]

func printAllSeqSumK(ind: Int,
                     op: inout [Int],
                     targetSum: Int,
                     currSum: inout Int,
                     inArray: [Int],
                     length: Int) {
    if ind == length {
        if  targetSum == currSum {
            print("foundTheSum-->", op)
        }
        return
    }
        
    op.append(inArray[ind])
    currSum += inArray[ind]
  
    printAllSeqSumK(ind: ind+1,
                    op: &op,
                    targetSum: targetSum,
                    currSum: &currSum,
                    inArray: inArray,
                    length: length)
    op.removeLast()
    currSum -= inArray[ind]

    printAllSeqSumK(ind: ind+1,
                    op: &op,
                    targetSum: targetSum,
                    currSum: &currSum,
                    inArray: inArray,
                    length: length)
}


let arrayInput = [4,8,4]
let length = arrayInput.count
var op: [Int] = []
let ind = 0
let targetSum = 8
var currSum = 0
printAllSeqSumK(ind: ind,
                op: &op,
                targetSum: targetSum,
                currSum: &currSum,
                inArray: arrayInput,
                length: length)

Leave a Comment

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