dfs专题

1、自然数的拆分问题

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数n。

输出格式

输出：若干数的加法式子。

输入输出样例

输入 #1

7

输出 #1

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

说明/提示

用回溯做，dfs的基本思路，dfs和bfs都是有套路的，多原理晓得了就是自己要多练几遍就知道了

代码

import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr ;
    public static void dfs(int index,int sum){
        if(sum <0){							//剪枝，将不合格的去掉
            return;
        }
        if(sum == 0 ){						//边界条件
            for(int i =1;i<=index -2;i++){
                System.out.print(arr[i]+"+");
            }
            System.out.println(arr[index-1]);
//            System.out.println(arr[index]);
         return;
        }
        for(int i =1;i<n;i++){
            if(i<arr[index-1]) continue;		//这个是为了防止更小的数字再次进入
            arr[index] =i;						//回溯的基本套路
            sum = sum -i;
//            index ++;
            dfs(index+1 ,sum);
//            index--;
//            arr[index] = 0;
            sum = sum+i;
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
         n = cin.nextInt();
         arr = new int[100];
        dfs(1,n);
        cin.close();
    }
}

dfs专题

原文：https://www.cnblogs.com/jwthong/p/12564541.html