找出集合中总和为n的所有子集

本文介绍了找出集合中总和为n的所有子集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是我想出的代码：

static void findNumbers(int[] list, int index, int current, int goal, String result) { if (list.length < index || current>goal) return; for (int i = index; i < list.length; i++) { if (current + list[i] == goal) { System.out.println(result + " " + String.valueOf(list[i])); } else if (current + list[i] < goal) { findNumbers(list, i + 1, current + list[i], goal, result + " " + String.valueOf(list[i])); } } }

使用以下名称调用：

findNumbers(array, starting_index, current_sum_till_now, target_sum, "");

有人可以帮我弄清楚这段代码的时间复杂度，我相信它是指数的。

Can someone help me figure out the time complexity of this code I believe its exponential.

解决此问题的最佳方法是什么？

What is the most optimal way to solve this problem? Is it using backtrack?

推荐答案

有人指出我做错了。我应该增加递归调用的复杂性，而我应该添加它们。所以 C（N）= C（N-1）+ C（N-2）+ ... 。然后，这将适用于 C（N-1）， C（N-2）等。这意味着

It has been pointed out that I've done a mistake. I were multiplying the complexities of recursive calls while I should have added them. So C(N) = C(N-1) + C(N-2) + .... The same would then apply to C(N-1), C(N-2), etc. This means that the complexity isnt' O(N!).

这使我从另一个角度考虑了算法看法。它正在检查每个可能的子集。由于存在 2 ^ N-1 个可能的子集（不考虑空子集），因此复杂度为 O（2 ^ N） ，我认为这是您最初的选择。

This have made me thinking on the algorithm from another point of view. It is checking every single possible subset. Since there are 2^N - 1 possible subsets (the empty subset is not taken into account), then the complexity is O(2^N), which I think is your original bet.