刚刚东方财富的题目，感觉可以用回溯，但是没做出来，有哪位同学帮忙写一下，万分感谢！
_________________________________________________________________________
更新一下，东方财富的原题还有第三个参数k，即返回所有组合中的第k项（组合按照数字大小排序，如果第一个数字相同，就使用第二个排序，一次类推）
如果没有第k项，则返回-1。我自己的代码如下，感觉还有可以优化的地方，请大佬指点！
public class solution2 {
static List<List<Integer>> res = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int n = in.nextInt();
int k = in.nextInt();
backtrack(N, n, 1, new Stack<>());
if (k > res.size()) {
System.out.println(-1);
return;
}
List<Integer> list = res.get(k - 1);
int count = 0;
for (Integer integer : list) {
System.out.print(integer);
if (count != n - 1) {
System.out.print(" ");
}
}
}
private static void backtrack(int target, int n, int start, Stack<Integer> track) {
if (sum(track) == target && track.size() == n) {
res.add(new ArrayList<>(track));
return;
}
if (track.size() == n) return;
for (int i = start; i <= 10; i++) {
track.add(i);
backtrack(target, n, start + 1, track);
track.pop();
}
}
private static int sum(Stack<Integer> trace) {
int sum = 0;
ArrayList<Integer> list = new ArrayList<>(trace);
for (Integer integer : list) {
sum += integer;
}
return sum;
}
}
全部评论
(1) 回帖