蓝桥杯-算法训练 加法分解 java递归求解

问题描述

　　给一个正整数n，输出它所有的正整数加法的分解方法。其中交换加数的位置视为不同的分解方案。按字典序输出。特别地，不分解也视为一种分解方案。

输入格式

　　输入共一行一个正整数n。

输出格式

　　输出若干行，为n的所有正整数加法分解方法。每种方案输出一行。对于一种方案，先输出n，再输出一个“=”。然后输出分解的各数，不同的数之间用“+”连接。

样例输入

5

样例输出

5=1+1+1+1+1
5=1+1+1+2
5=1+1+2+1
5=1+1+3
5=1+2+1+1
5=1+2+2
5=1+3+1
5=1+4
5=2+1+1+1
5=2+1+2
5=2+2+1
5=2+3
5=3+1+1
5=3+2
5=4+1
5=5

解题思路

每个输入的数字都由从1到比它小1的数字组成。由于输出重复允许，所以每次在目标输入的n上减去这些数字直到n变为0达成目标，输出算式。每次减去的值都是从从1到比它刚好小1的数字里面选择，以此为基础进行递归。递归的出口就是目标数刚好减为0。

import java.util.Scanner;

public class 加法分解 {
	static int x;
	public static void f(String s,int n) {
		if (n == 0) {
			System.out.println(x+"="+s.substring(1));//去除等号后第一个数字的符号位
			return ;}
		
		
           for(int i=1;i<=n;i++) {
        	   f(s+"+"+i,n-i);
           }

	}

	public static void main(String[] args) {
		Scanner s1=new Scanner(System.in);
		x=s1.nextInt();
		f("",x);

	}

}

答案输出