这似乎有效 - 我没有看到任何迹象表明您不想要现成的答案(我相信如果这是家庭作业,您会说明)所以这里是:
public class IsSumOf {
// set - The numbers allowed.
// total - The number I want to achieve.
// i - Where we are in the set.
// sum - List of numbers used so far.
// n - The number we just subtracted (or 0 if none).
// Note that sum and n are only used for the printing of the route.
private static boolean isSumOf(int[] set, int total, int i, LinkedList<Integer> sum, int n) {
// Found the set if we are now at 0.
boolean is = (total == 0);
// Look no further if no more to try.
if ( total > 0 ) {
// Look no further if we've exhausted the array.
if ( i < set.length ) {
// Try or consume this number in the set (or not) and try again.
is = isSumOf(set, total - set[i], i, sum, set[i] )
|| isSumOf(set, total - set[i], i+1, sum, set[i] )
|| isSumOf(set, total, i+1, sum, 0 ) ;
}
}
// Keep track of the route.
if ( is && sum != null && n != 0) {
// Add backwards so we get the order right when printed.
sum.addFirst(n);
}
return is;
}
// Jump-off point.
public static boolean isSumOf(int[] set, int total, LinkedList<Integer> sum) {
// Empty the list.
sum.clear();
// Start at 0 in the array.
return isSumOf(set, total, 0, sum, 0);
}
public static void main(String[] args) {
LinkedList<Integer> sum = new LinkedList<Integer>();
int[] a = {18, 10, 6};
int x = 18 + 10 + 6;
System.out.println(Arrays.toString(a)+" ("+x+") = "+(isSumOf(a, x, sum)?Arrays.toString(sum.toArray()):"-"));
x += 1;
System.out.println(Arrays.toString(a)+" ("+x+") = "+(isSumOf(a, x, sum)?Arrays.toString(sum.toArray()):"-"));
int[] b = {3,2};
x = 12;
System.out.println(Arrays.toString(b)+" ("+x+") = "+(isSumOf(b, x, sum)?Arrays.toString(sum.toArray()):"-"));
x += 1;
System.out.println(Arrays.toString(b)+" ("+x+") = "+(isSumOf(b, x, sum)?Arrays.toString(sum.toArray()):"-"));
int[] c = {2,3};
x = 12;
System.out.println(Arrays.toString(c)+" ("+x+") = "+(isSumOf(c, x, sum)?Arrays.toString(sum.toArray()):"-"));
x += 1;
System.out.println(Arrays.toString(c)+" ("+x+") = "+(isSumOf(c, x, sum)?Arrays.toString(sum.toArray()):"-"));
}
}
编辑打印所走的路线。
印刷:
[18, 10, 6] (34) = [18, 10, 6]
[18, 10, 6] (35) = -
[3, 2] (12) = [3, 3, 3, 3]
[3, 2] (13) = [3, 3, 3, 2, 2]
[2, 3] (12) = [2, 2, 2, 2, 2, 2]
[2, 3] (13) = [2, 2, 2, 2, 2, 3]