TCL笔试的一道算法题
定义整型数组，例如
int a[]={1,2,3,6,7,4,5,2,1}
再定义一个整型int sum = 0，sum的值为数组a中所有加起来和为sum的所有元素集合。例如当sum=5时，输出{5},{1,4},{2,3},{2,2,1},{1,1,3}
实现函数体（Java或者C语言）
void function(int sum){
}
备注：function函数的形参可以自定义
COOLBE
12 years, 7 months ago
Answers
void function(int sum){
int i, j, k;
int solution[9], currentSum, height;
int ifBack;
//sort by ascending order
for(i = 0; i < 8; i++)
{
for(j = 0; j < 8-i; j++)
{
if(a[j] > a[j+1])
{
k = a[j];
a[j] = a[j+1];
a[j+1] = k;
}
}
}
currentSum = 0;
height = 0;
i = 0;
//search
do{
if(currentSum + a[i] == sum)
{
height++;
currentSum += a[i];
solution[height-1] = i;
printf("{");
for(k = 0; k < height; k++)
{
printf("%d ", a[solution[k]]);
}
printf("}\n");
height--;
currentSum -= a[i];
ifBack = 0;
}
else if(currentSum + a[i] < sum)
{
height++;
solution[height-1] = i;
currentSum += a[i];
ifBack = 0;
}
else
{
height--;
ifBack = 1;
if(height >= 0)
{
currentSum -= a[solution[height]];
}
}
if(ifBack == 1)
{
if(height >= 0)
{
i = solution[height]+1;
while(i > 8)
{
height--;
if(height >= 0)
{
currentSum -= a[solution[height]];
i = solution[height]+1;
}
else
{
break;
}
}
}
}
else
{
i++;
while(i > 8)
{
height--;
if(height >= 0)
{
currentSum -= a[solution[height]];
i = solution[height]+1;
}
else
{
break;
}
}
}
}while(height >= 0);
}
神奇IP君
answered 12 years, 7 months ago