深度优先遍历------部分和问题
程序员文章站
2023-12-22 19:38:58
...
代码如下:
运行结果如下:
package com.chapterOne.exercise; import java.util.ArrayList; import java.util.List; /** * Created by yangjianzhou on 2014/8/15 19:56. * TODO : 给定a1,a2,a3,......an,判断是够可以从中选取若干个数,使它们的和恰好为k */ public class PartSum { private static int n = 9; private static int target = 23; private static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}; private static List<String> result = new ArrayList<String>(); public static void main(String[] args) { System.out.println(dfs(0,0)); for(String str : result){ System.out.print(str + "---"); } } private static boolean dfs(int i, int sum) { if (i == n) { return sum == target; } if (dfs(i + 1, sum)) { return true; } if (dfs(i + 1, sum + arr[i])) { result.add(String.valueOf(arr[i])); return true; } return false; } }
运行结果如下:
true 9---8---6---