Find all the numbers within a range whose digits add up to a certain target In an interview I was asked the following problem:


  Given a range of numbers (0 - 100) or (0 - 1000), find all the numbers whose digit add up to 5.


I started off with a brute force way to iterate over all the numbers and filter out numbers whose digits do not add up to 5. The numbers remaining will be the answer. 

It seems like that wasn't the desired solution. After thinking about the problem a little bit I realized another approach would be to use recursion to generate all the numbers until a particular "digit-size".

For example, if we are asked to generate all the numbers that between 0 and 100 that add up to 5, we can generate all numbers from 'digit-size=1' to 'digit-size=3' that add up to 5.

It will be great if this approach could be reviewed.

    public class FindAllNumbersWithCertainDigitSum {
       public List&lt;Integer&gt; getAllNumbersThatSumToTarget(int digitSize, int target) {
          List&lt;Integer&gt; candidates = new ArrayList&lt;&gt;();
          int accumulatedSum = 0;
          helper(digitSize, target, candidates, accumulatedSum);
          return candidates; 
     }

     private void helper(int digitSize, int target, List&lt;Integer&gt; candidates, int accumulatedSum) {
         //Base case: No more digits to consider and nothing else to add
         if(digitSize == 0 &amp;&amp; target == 0) {
             candidates.add(accumulatedSum);
         } 
       //There is nothing else to add but there are more digits to consider that will be multiples of 10
       else if(digitSize != 0 &amp;&amp; target == 0) {
             helper(digitSize - 1, target, candidates, accumulatedSum * 10);
         } 
      //The digits did not add up to the target, return without doing anything 
      else if(digitSize == 0 &amp;&amp; target != 0) {
             return;
         } else {
            //Iterate from target down to zero and recursively get the remaining digits if the first digit is the target.
             for(int current = target; current &gt;= 0; current--) {
                 helper(digitSize - 1, target - current, candidates, accumulatedSum*10 + current);
             }
         }

      }

     public static void main(String[] args) {
        FindAllNumbersWithCertainDigitSum s = new FindAllNumbersWithCertainDigitSum();
        //Get all numbers from 0 - 999(maxDigitSize == 3) that add up to 5
        s.getAllNumbersThatSumToTarget(3, 5)
         .stream()
         .forEach(System.out::println);
      } 
}
Just a idea...

There are 7 sets of digits that can constuct numbers that add up to 5.

a = [1, 1, 1, 1, 1]
b = [2, 1, 1, 1]
c = [2, 2, 1]
d = [3, 1, 1]
e = [3, 2]
f = [4, 1]
g = [5]


Then:
let r be the sets in (a...g) that has size &lt; log(max)

Pad each set in r with zeroes so that all set sizes are log(max)

The answer is permutations of the sets that are in the range min - max.