c# - Algorithm to calculate the number of combinations to form 100

Question

I am struck in a tricky situation where I need to calculate the number of combinations to form 100 based on different factors.

Those are

• Number of combinations
• Multiplication factor
• distance

Sample input 1: (2-10-20)

It means

• list the valid 2 way combination to form 100.
• the distance between the combination should be less than or equal to 20.
• And all of the resultant combination must be divisible by the given multiplication factor 10

Output will be

[40,60]

[50,50]

[60,40]

here [30,70],[20,60] are invalid because the distance is above 20.

Sample Input 2: [2-5-20]

[40,60]

[45,55]

[50,50]

[55,45]

[60,40]

I would really appreciate if you guided me to the right direction.

Cheers.

Answer 1

I hope it's not a homework problem!

    def combinations(n: Int, step: Int, distance: Int, sum: Int = 100): List[List[Int]] =
      if (n == 1) 
        List(List(sum))
      else 
        for {
          first <- (step until sum by step).toList
          rest <- combinations(n - 1, step, distance, sum - first)
          if rest forall (x => (first - x).abs <= distance)
        } yield first :: rest