公司一道面试题,求大神给思路!
输入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"); }