部分和：
给定整数序列a1,a2,...,an,判断是否可以从中选出若干数,使它们的和恰好为k.
样例：
输入
n=4
a={1,2,4,7}
k=13
输出
Yes (13 = 2 + 4 + 7)
思路：
已有n个数字，用数组a存放，变量cur从指向第0个下标元素开始不断往后扫描数组，这个时候有两种选择状态：
1.不要当前元素，cur+1继续递归。
2.要当前元素，放入ArrayList集合中记录曾经选了那个元素，我们的k减去a[cur]当前元素值，继续往后扫描cur+1，这里还得退回到平行状态，回溯操作remove(a.size()-1)。
3.出口，如果k < 0 或者 cur == a.length时直接return，如果k == 0代表ArrayList集合里的元素刚好凑齐k，直接打印输出。
1 import java.util.ArrayList; 2 import java.util.Scanner; 3 4 public class Seven_13dfs竞赛题部分和 { 5 static int kk; 6 private static void dfs(int[] a, int k, int cut, ArrayList<Integer> ints){ 7 if(k == 0){ 8 System.out.print("Yes ("+kk+" = "); 9 for(int i = 0; i < ints.size(); i++){ 10 System.out.print(ints.get(i)+(i==ints.size()-1 ? "" : " + ")); 11 } 12 System.out.println(")"); 13 } 14 if(k < 0 || cut == a.length) 15 return; 16 17 //不要的情况 18 dfs(a, k, cut+1, ints); 19 20 //要的情况 21 ints.add(a[cut]); 22 int index = ints.size()-1; 23 dfs(a, k-a[cut], cut+1, ints); 24 ints.remove(index); 25 } 26 public static void main(String[] args) { 27 Scanner in = new Scanner(System.in); 28 int n = in.nextInt(); 29 int[] a = new int[n]; 30 for(int i = 0; i < n; i++){ 31 a[i] = in.nextInt(); 32 } 33 int k = in.nextInt(); 34 kk = k; 35 dfs(a, k, 0, new ArrayList<Integer>()); 36 } 37 }
原文：https://www.cnblogs.com/z1110/p/12609555.html