找出集合中总和为n的所有子集 [英] Find all subsets of a set that sum up to 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.

这篇关于找出集合中总和为n的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！