公司一道面试题,求大神给思路!
输入1234输出
1
2
3
4
12
13
14
23
24
34
123
124
234
1234
我的思路是,全排列,然后按条件输出,但是空间复杂度和时间复杂度都挺高,求其他思路!
程序代码:
#include "stdio.h"
#include "string.h"
char f_p[] = {"%.0s"};
char s[8];
void f (char* num, int len, int len_r, int c, int c_r, int* c_s)
{
int i;
for (i=0; i<len-(c-1) && c>0; i++)
{
f_p[2] = 1 + 0x30;
printf (f_p, &num[i]);
(*c_s)++;
strncat (s, &num[i], 1);
if (*c_s == c_r)
{
printf ("\n");
(*c_s) = 0;
if ((s[c_r-1] == (len_r+0x30)) && (c_r>1))
{
int i;
for (i=c_r-1; i>0; i--)
{
if (s[i-1]+1 == s[i])
{
continue;
}
else
{
break;
}
}
if (i==0)
{
s[0] = 0;
return;
}
else
{
int count;
s[i-1] = 0;
count = (c_r-1) - i + 1;
f_p[2] = c_r - (count + 1) + 0x30;
printf (f_p, s);
(*c_s) = c_r - (count+1);
}
}
else
{
s[c_r-1] = 0;
f_p[2] = c_r-1 + 0x30;
printf (f_p, s);
(*c_s) = c_r-1;
}
}
f (&num[i+1], len-1-i, len_r, c-1, c_r, c_s);
}
}
int main (int argc, char** argv)
{
char f_num[] = {"1234"};
int len;
int c_s;
int i;
c_s = 0;
len = strlen (f_num);
for (i=0; i<len; i++)
{
f (f_num, len, len, i, i, &c_s);
}
return 0;
}


程序代码:#include <stdio.h>
#include <malloc.h>
#include <string.h>
void sub_show_comb(char * set, int n, char * stack, int count, int index)
{
int i;
if(index == count)
{
puts(stack);
return;
}
for(i = 0; i <= n - count + index; i++)
{
stack[index] = set[i];
sub_show_comb(set + i + 1, n - i - 1, stack, count, index + 1);
}
}
void show_comb(char * set)
{
char * stack;
int n, i;
n = strlen(set);
stack = (char *)malloc(n + 1);
for(i = 1; i <= n; i++)
{
stack[i] = '\0';
sub_show_comb(set, n, stack, i, 0);
}
free(stack);
}
int main()
{
char s[] = "1234";
show_comb(s);
return 0;
}

程序代码:#include <stdio.h>
void comb(char *s,char *d,int l,int p)
{
int i,j;
char a[10];
for(i=0;d[i];i++)a[i]=d[i];
a[i]=0;
if(i==l)
printf("%s,",a);
else
{
for(j=p;s[j];j++)
{
a[i]=s[j];
a[i+1]=0;
comb(s,a,l,j+1);
}
}
}
void main()
{
char a[10],b[]="1234";
int i;
a[0]=0;
for(i=0;b[i];i++)comb(b,a,i+1,0);
printf("\n");
}
