你已经非常接近了,但你需要撤消temp.add(i)
在继续迭代之前。这最容易使用Deque https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html代替List https://docs.oracle.com/javase/8/docs/api/java/util/List.html.
我会这样写:
public static List<List<Integer>> combosWithSum(int sum) {
if (sum < 0)
throw new IllegalArgumentException("Sum cannot be negative: " + sum);
if (sum == 0)
return Collections.emptyList();
List<List<Integer>> result = new ArrayList<>();
buildCombosWithSum(sum, new ArrayDeque<>(), result);
return result;
}
private static void buildCombosWithSum(int sum, Deque<Integer> combo, List<List<Integer>> result) {
for (int num = sum; num > 0; num--) {
combo.addLast(num);
if (num == sum)
result.add(new ArrayList<>(combo));
else
buildCombosWithSum(sum - num, combo, result);
combo.removeLast();
}
}
Test
combosWithSum(5).forEach(System.out::println);
Output
[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 3]
[2, 2, 1]
[2, 1, 2]
[2, 1, 1, 1]
[1, 4]
[1, 3, 1]
[1, 2, 2]
[1, 2, 1, 1]
[1, 1, 3]
[1, 1, 2, 1]
[1, 1, 1, 2]
[1, 1, 1, 1, 1]
要按照问题中显示的顺序获得结果,请在前面添加以下行return result;
:
result.sort(Comparator.comparingInt(List::size));
[5]
[4, 1]
[3, 2]
[2, 3]
[1, 4]
[3, 1, 1]
[2, 2, 1]
[2, 1, 2]
[1, 3, 1]
[1, 2, 2]
[1, 1, 3]
[2, 1, 1, 1]
[1, 2, 1, 1]
[1, 1, 2, 1]
[1, 1, 1, 2]
[1, 1, 1, 1, 1]