java - 减少递归子集求和算法的运行时间

Question

我有一个递归 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秒)

我正在寻找更好的方法来实现这个算法。

Answer 1

一些小的优化，如果我理解正确的话:

 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 节省一点时间。如果你想变得花哨，你可以使用多线程。