每日一题 求和

1.题目解析 

求和_牛客题霸_牛客网 (nowcoder.com) 

这一题，主要描述的就是求满足和为m的子序列，对与子序列的问题可以使用决策树。

2.思路分析

决策树如下图所示:

1. 递归结束条件： 当当前和 sum 等于目标和 m 时，说明找到了一个满足条件的组合，将当前组合加入结果列表中，并返回。
2. 剪枝条件： 如果当前和 sum 已经大于目标和 m，或者当前数字 start 已经大于了最大数 n，则无需继续搜索，直接返回。
3. 选择当前数字： 将当前数字 start 加入当前组合 path 中，并递归搜索下一个数字，同时更新当前和 sum。
4. 不选择当前数字： 直接递归搜索下一个数字，不将当前数字加入当前组合中。

基于以上思路，我们可以编写出如下的伪代码：

function dfs(start, path, sum):
    if sum == m:
        将当前组合 path 加入结果列表中
        返回

    if sum > m 或者 start > n:
        返回

    选择当前数字 start
    将 start 加入 path 中
    递归调用 dfs(start + 1, path, sum + start)
    将 start 从 path 中移除（回溯操作）

    不选择当前数字 start
    递归调用 dfs(start + 1, path, sum)
 

 3.代码实现

import java.util.*;

public class Main{
    private static int n;//所有数的最大值
    private static int m;//要求的和
    private static boolean[] vis;//标记是否被使用
    private static int sum;//被选中的元素之和
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            n = sc.nextInt();
            m = sc.nextInt();
            vis = new boolean[n + 1];
            sum = 0;
            dfs(1);//从第一个元素开始递归(相当于决策树的根节点)
        }
    }
    private static void dfs(int x){
        if(sum == m){//找到一种情况
            for(int i = 1; i <= n;i++){
                if(vis[i]){//被选择的都打印出来
                    System.out.print(i + " ");
                }
            }
            System.out.println();//一次结果输出后换行
            return;
        }
        if(sum > m || x > n) return;//不符合条件的情况，剪枝
        //1.x位置的选 相当与前序遍历，先处理根在递归
        sum += x;
        vis[x] = true;//标记已经被使用
        dfs(x + 1);
        sum -= x;
        vis[x] = false;//回溯的时候初始状态
    
        //2.不选
        dfs(x + 1);
    }
}