题解 | #求和#

import java.util.*;

public class Main {
    /**
     * 解题思路: (深度优先算法dfs)
     * 还是那句总结的话:
     * 寻找最优多用动态规划
     * 输出所有情况多用dfs
     * 因为本题是需要按字典序排序输出,因此我们在dfs之前对于要穷举的元素按字典序进行排序即可,
     * 只不过本题是数字,因此我们不需要进行排序,因为按从 1 递增的顺序就是按字典序的顺序穷举
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            Deque<Integer> temp = new LinkedList<>();
            dfs(n,m,temp,0,0);
        }
    }

    /**
     * 总体思路较为简单,但是本解法中有以下两个较为巧妙的点
     * 1: 因为题目中是需要按照字典序进行输出,且数字不可以重复用,因此我们这里就在 dfs 的参数上面增加了
     *    foreNum 参数,来记录前一个数字的值,方便我们满足以上两个条件,但是这个就要求我们调用的时候这个
     *    参数传入 0 ,就是从 1 开始到 maxNum 的数字可用
     * 2: 本 dfs 我们可以发现没有判断 curSum > target 的情况,因为我们在循环的过程中加了如下判断
     *    (target-curSum) == i || (target-curSum) > 2*i
     *    因为数字是递增的且不会重复,因此要想满足继续递归下去还有可以满足的数字集合,因此只有以下两种情况
     *    1) curSum + 要添加的数字 == target
     *    2) (target-curSum) > 2*i 
     *    这个条件的解释为 因为 curSum + 要添加的数字 != target,所以我们至少要添加两个数字,又因为数
     *    字是递增的且不会重复,因此这两个数字的和最少为 2*要添加的数字+1 ,因此若 
     *    target-curSum < 2*要添加的数字+1 则绝对不可能出现两个数字满足该组数字相加为 target,因此
     *    不需要进行dfs下去了,少了很多次无用的遍历
     *    由以上这两个条件的筛选之后,就不可能出现 curSum > target 的情况了
     * @param maxNum   可用数字的最大值
     * @param target   目标值
     * @param temp     临时记录前面所选数字
     * @param foreNum  前一个选中的数字
     * @param curSum   已选中的数字的和
     */
    private static void dfs (int maxNum, int target, Deque<Integer> temp, int foreNum, int curSum) {
        if (curSum == target) {
            for (int n : temp) {
                System.out.print(n + " ");
            }
            System.out.println();
        }

        for (int i = foreNum+1; i <= maxNum; i++) {
            if ((target-curSum) == i || (target-curSum) > 2*i) {
                temp.addLast(i);
                dfs(maxNum,target,temp,i,curSum+i);
                //回溯
                temp.pollLast();
            }
        }
    }
}