欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数的拆分(DFS的应用)

程序员文章站 2022-07-16 16:03:00
...

数的拆分(DFS的应用)

import java.util.Scanner;
public class Main{
	  static int n,m,k,sum=0;
	  static int []res=new int [100];//保存结果的数组
	 
		public static void main(String[] args) {
		  Scanner scanner=new Scanner(System.in);
		  n=scanner.nextInt();
		
		  k=1;
		  dfs(0,n);
		  
		}
		public static void dfs(int step,int l)
		{
			
			if (l==0)
			{
				for(int i=1;i<k-1;i++)
				{
					System.out.print(res[i]+"+");
				}
				System.out.println(res[k-1]);
				return ;
			}
			
			for(int i=1;i<=l;i++)
			{
				if ((res[k-1]<=i)&&i<n)
				{
					l=l-i;
					res[k++]=i;
					dfs(step+1, l);
					k--;
					l=l+i;
				}
			}
		
		
		}
		
		

	}
相关标签: DFS搜索算法