蓝桥杯算法训练VIP-和为T-题解（Java代码）深搜DFS

import java.util.ArrayList;
import java.util.Scanner;

public class 和为T{

    static int sum, ans = 0;
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        sum = sc.nextInt();
        dfs(n - 1, 0, "");
        System.out.println(ans);
    }

    /**
     * 
     * @param i
     *            当前数
     * @param s
     *            取的数的和
     * @param str
     *            记录我取了那些数
     */
    public static void dfs(int i, int s, String str) {
        // 边界
        if (i == -1) {
            // !str.equals("")表示我最少取了一个 如果输入的是0，那么我可以一个数都不取，但题目是不允许这种情况的
            if (!str.equals("") && s == sum) {
                ans++;
                System.out.println(str);
            }
            return;
        }
        // 不取的情况
        dfs(i - 1, s, str);
        // 取的情况
        dfs(i - 1, s + arr[i], arr[i] + " " + str);
    }
}