减少我的递归子集求和算法的 运行 时间
Decreasing the run time for my recursive subset sum algorthim
我有一个递归 DFS 算法，可以正确计算子集总和的数量。然而，这种方法的 运行 时间是荒谬的，而且是指数级的。例如，当 arr 包含以下集合时。我们要查找的总和是 50。arr 删除了所有重复项和大于或等于 50 的数字。然后对数组进行排序。
21
3个
42
10
13
17
33
26
19
7
11
30
24
2个
5
arr 包含排序的单词列表
k是数组的初始大小
sum 是我们在子集中寻找的总和，在这个例子中它是 50
public static void recDfs(ArrayList<Integer> arr, int k, int sum) {
if (sum == 0) {
counter++;
return;
}
if (sum != 0 && k == 0) {
return;
}
recDfs(arr, k - 1, sum - arr.get(k - 1));
recDfs(arr, k - 1, sum);
}
这将非常快速地给出正确的结果，在下面发布
经过的时间：= 0.004838有 51 个子集总和为 50
构建成功（总时间：0 秒）
然而，当我们在数组中有一个新集合时，这个算法会呈指数增长，例如。
99
49
1个
7
23
83
72
6个
202
78
26
79
351
34
107
76
38
50
32
62
71
9
101
77
81
92
89
66
97
57
33
75
68
93
100
28
42
59
29
14
122
24
60
2个
37
192
73
84
31
4个
87
65
19
当我们使用新数组再次调用 recDfs 时，新数组也经过排序并删除了重复项，总和为 107，运行 时间是荒谬的，但是打印了正确数量的子集。
经过的时间：= 19853.771050有 1845 个子集总和为 107
构建成功（总时间：330分54秒）
我正在寻找更好的方法来实现这个算法。
一些小的优化，如果我理解正确的话：
public static void recDfs(int[] arr, int k, int sum) {
if (sum < 0) return;
if (sum == 0) {
counter++;
return;
}
if (k == 0) {
return;
}
recDfs(arr, k - 1, sum - arr[k - 1]);
recDfs(arr, k - 1, sum);
}
如果我的解释正确，如果总和小于 0，您可以放弃分支，这样可以节省很多时间。 （如果有负数则无法完成）其他较小的优化是使用 int 数组。这应该比使用整数 ArrayList 节省一点时间。如果你想变得花哨，你可以使用多个线程。
我有一个递归 DFS 算法，可以正确计算子集总和的数量。然而，这种方法的 运行 时间是荒谬的，而且是指数级的。例如，当 arr 包含以下集合时。我们要查找的总和是 50。arr 删除了所有重复项和大于或等于 50 的数字。然后对数组进行排序。
21 3个 42 10 13 17 33 26 19 7 11 30 24 2个 5
arr 包含排序的单词列表
k是数组的初始大小
sum 是我们在子集中寻找的总和，在这个例子中它是 50
public static void recDfs(ArrayList<Integer> arr, int k, int sum) {
if (sum == 0) {
counter++;
return;
}
if (sum != 0 && k == 0) {
return;
}
recDfs(arr, k - 1, sum - arr.get(k - 1));
recDfs(arr, k - 1, sum);
}
这将非常快速地给出正确的结果，在下面发布
经过的时间：= 0.004838有 51 个子集总和为 50 构建成功（总时间：0 秒）
然而，当我们在数组中有一个新集合时，这个算法会呈指数增长，例如。
99 49 1个 7 23 83 72 6个 202 78 26 79 351 34 107 76 38 50 32 62 71 9 101 77 81 92 89 66 97 57 33 75 68 93 100 28 42 59 29 14 122 24 60 2个 37 192 73 84 31 4个 87 65 19
当我们使用新数组再次调用 recDfs 时，新数组也经过排序并删除了重复项，总和为 107，运行 时间是荒谬的，但是打印了正确数量的子集。
经过的时间：= 19853.771050有 1845 个子集总和为 107 构建成功（总时间：330分54秒）
我正在寻找更好的方法来实现这个算法。
一些小的优化，如果我理解正确的话：
public static void recDfs(int[] arr, int k, int sum) {
if (sum < 0) return;
if (sum == 0) {
counter++;
return;
}
if (k == 0) {
return;
}
recDfs(arr, k - 1, sum - arr[k - 1]);
recDfs(arr, k - 1, sum);
}
如果我的解释正确，如果总和小于 0，您可以放弃分支，这样可以节省很多时间。 （如果有负数则无法完成）其他较小的优化是使用 int 数组。这应该比使用整数 ArrayList 节省一点时间。如果你想变得花哨，你可以使用多个线程。