JAVA program to find all numbers whose sum of digits is equal to an input number

ALGORITHM:

The problem is to input a number and find all numbers whose digits sum is equal to the input number.

i.e. if the input number is 5 then program should print numbers 5 14 23 32 41.

The problem can be solved by doing a recursive algorithm given below:

1. Start with first digit 1 to 9
2. Check whether the number digit's sum has exceeded the target or has reached the target; if it has reached target then print the number; if so return from the function.
3. If the digit's sum is less than target then try adding digits 1 to 9 to the LSB of the number and recurse the function(from step 2) for each such made new numbers.

The program of algorithm is given below since java has a stack limit of about 1k bytes the program won't work for large numbers :P.

CODE:

import java.util.Scanner;

public class digitSum{

    static boolean isInArray(int[] a,int ele){
        for(int i=0;i<a.length;i++)
            if(a[i]==ele)
                return false;
        return true;
    }

    static int findSum(int[] ar,int end){
        int sum=0;
        for(int i=0;i<=end;i++)
            sum+=ar[i];
        return sum;
    }

    static void printNum(int[] ar,int index,int num){
       
        int sum = findSum(ar,index);
        int diff = num-sum;
        if(diff<0)
            return;
        if(diff==0){
            for (int i=0;i<=index;i++)
                System.out.print(ar[i]);
            System.out.println();  
            return;
        }
        for(int i=1;i<10;i++){
            if(isInArray(ar,i)){
                ar[index+1]=i;
                printNum(ar,index+1,num);
            }
        }
       
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("\nEnter the number: ");
        int num=in.nextInt();
        int[] ar = new int[9];
        for (int i=1;i<=9;i++ ) {
            ar[0]=i;
            printNum(ar,0,num);
        }
    }
}

OUTPUT:

Enter the number: 8
125
134
143
152
17
215
251
26
314
341
35
413
431
512
521
53
62
71
8