嗨,大家好,我在一个问题上困扰了很长时间-
这里是 -



我的方法-考虑大小为3的数组-{10,11,12}。考虑第一个元素-我有2个选择不采用它。因此,我为第一个要素工作,其余工作由Recusion完成。

int helper(int in[],int si,int n,int output[][20]){
                       //si - starting index , n  - size
  if(si == n){
    output[0][0] = 0;        //using 0 for null
    return 1;               //helper returns the number of subsets of array
  }

  int smallSize = helper(in,si+1,n,output);
  for(int i =0;i<smallSize;i++){
    output[i+smallSize][0] = in[si];
    for(int k = 0;k<4;k++){
      output[i+smallSize][k+1] = output[i][k];
    }
  }
  return smallSize*2;
}

int subset(int input[], int n, int output[][20]) {
  return helper(input,0,n,output);
}

我想将所有子集存储在二维数组输出中,并返回子集的数量。

我似乎得到零?

最佳答案

您的基本情况是不正确的。它必须代表一个空数组。不知道是否可以使用本机数组数据结构来执行此操作。

通常,有多种方法可以解决“所有子集”(或“所有组合”)问题。 Google以其他方式表示“集合的所有组合”(以及相关的“列表的所有排列”)。

这些类型的问题具有指数复杂度(对于排列而言,它是阶乘复杂度),因此请注意输入大小N。

您的想法正确,但是由于使用的是本机数组,因此缺少一些东西。由于已经标记了C++,因此如果使用STL,它将使工作变得更加轻松。

这是递归执行此操作的一种方法:

vector<vector<int> > AllCombinations(vector<int> input) {
  //base case
  if(0 == input.size()) {
    //1 element of empty/null set
    return vector<vector<int> >(1, vector<int>());
  }
  //recursion case
  const int last = input.back();
  input.pop_back();
  vector<vector<int> > result = AllCombinations(input);
  result.reserve(result.size() * 2);
  //add last element to previous result
  const size_t resultSize = result.size();
  for(size_t i = 0; i < resultSize; ++i) {
    vector<int> tmp = result[i];
    tmp.push_back(last);
    result.push_back(tmp);
  }
  return result;
}

复杂度: O(2 ^ N)

关于c++ - 使用递归C++返回数组的子集,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/46695719/

10-11 23:02
查看更多