Tìm số các số có k chữ số chỉ gồm 4 chữ số trên, sao cho tổng các chữ số là N

Để tránh topic này trở thành topic hỏi bai tập thì @John_Smith đưa ra một vài ý tưởng xem, hoặc dự đoán sẽ làm thế nào để mọi người hướng dẫn dễ hơn hoặc bắt đầu hỏi bằng những vấn đề nhỏ của bài toán, thay vì hỏi toàn bộ bài tập

Hiện tại e đã làm được bài toán bằng cách vét cạn. Nhưng chưa biết làm sao để làm bằng stack

Code vét cạn của e

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.Scanner;



public class vetcan {
    static int n,k;
    static int [] arr = {0,1,2,5};
    public static int sum(int [] a)
    {
        int sum = 0;
        for (int b : a)
        {
            sum += b;
        }
        return sum;
    }
  public static void binary (int []a,int i)
    {
        
        int v;
        for ( v = 0; v < 4 ; v++)
        {
            a[i] = arr[v];
            if (i < k-1) binary(a, i+1);
            else if (sum(a) == n && a[0] != 0) 
            {
                for (int b: a)
                {
                    System.out.print(b);
                }
                System.out.println("");
            }
        }
    }
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.print("Nhap k: ");
       k = sc.nextInt();
       System.out.print("Nhap N: ");
       n = sc.nextInt();
        int [] a = new int[k];
        binary(a, 0);   
    }
}

ược bài toá

Có lẽ dùng stack hơi khó với bài này, dùng Queue với thuật toán loang:

bạn sẽ gọi hàm

gen(i, x) tức là gen chữ số thứ i, với tổng là x (gần giống quy hoạch động). Thì gen(i, x) sẽ gọi gen(i - 1, x - digit) với digit = {0, 1, 2, 5}. Độ phức tạp là O(N*k)