子序列Subset Sum Problem(二)

发布于:2021-09-18 14:45:58

给定一个数组和子数组长度,打印该数组中所有等于长度的组合子序列
如图:
输入值:{1,2,3,4,5}
输出值:见根节点


#include
#include
#include
using namespace std;
void combinationUtil(int arr[],int data[],int start,int end,int index,int r)
{
/* arr[] --->输入数组
data[] ---> 储存当前的组合
start & end ---> Staring and Ending indexes in arr[]
index ---> Current index in data[]
r ---> 要被打印的组合长度 */

if(index==r)
{
vector value;
for(int i=0;i {
// printf("%d ",data[i]);
value.push_back(data[i]);

}
// printf("
");
//***************扩展,将其变成subSetSum 问题,例如三数和等于0的子序列******************
int d=std::accumulate(value.begin(),value.end(),0);
if(d==0)
{
for(auto v:value)
{
printf("%d ",v);
}
printf("
");
}

}
for(int i=start;i<=end && end-i+1>=r-index;i++)
{
data[index]=arr[i];
combinationUtil(arr,data,i+1,end,index+1,r);
}
}
void printCombination(int arr[],int n,int r)
{
int data[r];
combinationUtil(arr,data,0,n-1,0,r);

}
int main()
{
int arr[]={1,1,1,-2,2};
int r=3;
int n=sizeof(arr)/sizeof(arr[0]);
printCombination(arr,n,r);
return 0;
}



将其代码也可以扩展为三数和问题,以及输出所有等于sum的任意长度序列问题
如输出三数和等于0的序列
input:{1,1,1,-2,2}

相关推荐