数的拆分(DFS的应用)
程序员文章站
2022-07-16 16:03:00
...
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;
}
}
}
}
下一篇: 深度优先搜索