Combination Sum in Scala with Recursive Approach


  • 0
    T
    object Solution {
        var candidates: List[Int] = List()
        var target: Int = 0
    
        def possibleNumbers(result: List[Int]): List[Int] = result match {
          case Nil => candidates
          case _ =>  candidates.filter(x => ((x<= (result.head)) && (x<= (target-(result.sum)))))
        }
    
        def nextResult(prevResult: List[Int]): List[List[Int]] = prevResult match {
          case x if (x.sum==target) => List(x)
          case _ => for {
              possibleNumber <- possibleNumbers(prevResult)
              result <- nextResult(possibleNumber :: prevResult)
              } yield result
        }
    
        def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
            this.candidates = candidates.toList
            this.target = target
            nextResult(List())
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.