题目
代码
import java.util.Scanner; public class Main2dfs { private static int n, a[], k; /** * * 4 1 2 4 7 13 4 1 2 4 7 15 */ public static void main(String[] args) { // 输入n, a[], k Scanner in = new Scanner(System.in); n = in.nextInt(); a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } k = in.nextInt(); if (dfs(0, 0)) { System.out.println(true); } else { System.out.println(false); } } // 已经从前i项得到了和sum，然后对于i项之后的进行分支 private static boolean dfs(int i, int sum) { System.out.println("i:" + i + " sum:" + sum); // 如果前n项都计算过了，则返回sum是否与k相等 if (i == n) { return sum == k; } // 不加上a[i]的情况 if (dfs(i+1, sum)) { return true; } // 加上a[i]的情况 if (dfs(i+1, sum+a[i])) { return true; } // 无论是否加上a[i]都不能凑成k就返回false return false; } }
图解
题目和代码出处
excel表单方便看自己写的
