嗨,大家好,我在一个问题上困扰了很长时间-
这里是 -
我的方法-考虑大小为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/