Logic maths problem

[Cags]

I've recently been coding various logic puzzles and I've ran into a tricky problem. I need to take a number between 1 & 45 and work out which (unique) numbers between 1 & 9 can be added up to achieve this number. For example 17 can only be made using 8 & 9. Unfortunately I can't think of an efficient way of doing it.

[IngisKahn]

List<int> FindCrazyNumbers(int solution)
{
   if (solution < 1 || solution > 45) return null;
   List<int> ret = new List<int>();
   int sum = 0, add = 10;
   while (sum != solution)
       if (sum + --add <= solution)
       {
           sum += add;
           ret.Add(add);
       }
   return ret;
}

[Cags]

Thanks for the suggestion, thats an interesting solution however not quite appropriate. I guess its my fault really as I neglected to mention a critical part that was causing me trouble. Your method will alwas find the solution using the least amount of numbers wheras what I need is to find a solution with a specified amount of values. Using the example I gave before what I meant to say was that 17 with 2 values must be 8 + 9. But I might also need to produce 17 in 3 values (which could be quite a few things, (9,1,7),(9,2,6).... etc...

[JumpyNET]

A solution

 

Just add a button and a listbox to your project and you can try this out.

 

   Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

       FindFactors(17, 3)

   End Sub


   Private Sub FindFactors(ByVal Sum As Integer, ByVal NumberOfFactors As Integer)

       Dim Factors(NumberOfFactors + 1) As Integer
       Dim i As Integer, j As Integer
       For i = 1 To NumberOfFactors Step 1
           Factors(i) = 9
       Next
       Factors(0) = 2
       Factors(NumberOfFactors) = 10

       Do While Factors(0) = 2
           If Factors(1) = 1 Then
               Exit Do
           End If
           For i = 1 To NumberOfFactors Step 1
               If Factors(i) = 1 Then
                   Factors(i - 1) -= 1
                   For j = i To NumberOfFactors Step 1
                       Factors(j) = Factors(i - 1)
                   Next
                   Exit For
               Else
                   If i = NumberOfFactors Then
                       Factors(i) -= 1
                   End If
               End If
           Next

           'Print correct answers
           Dim Suggestion As String = ""
           Dim AddUp As Integer = 0
           For j = 1 To NumberOfFactors Step 1
               AddUp = AddUp + Factors(j)
               Suggestion = IIf(j = 1, "", Suggestion & "+") & Factors(j)
               If j = NumberOfFactors Then
                   Suggestion = Suggestion & "=" & AddUp
               End If
           Next
           If AddUp = Sum Then
               ListBox1.Items.Add(Suggestion)
               Application.DoEvents()
           End If

       Loop


   End Sub

 

If you wanna see how it works you can comment out these two lines at the end and the program will print out all the possibilities it tries.

 

           'If AddUp = Sum Then
           ListBox1.Items.Add(Suggestion)
           Application.DoEvents()
           'End If

[Cags]

Hmm.. that works, unfortunately it uses numbers more than once atm, but with that as a start I should be able to work out a perfect solution.

[IngisKahn]

BTW: Factors are used in multiplication, addends are used in addition. :)