标题: 2010 年中兴面试题 [打印本页] 作者: 秦静静 时间: 2013-8-16 11:17 标题: 2010 年中兴面试题 编程求解：输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来.作者: 王萍 时间: 2013-8-16 13:05
This is acombination generation problem.void findCombination(int n, int m) { if (n>m) findCombination(m, m); int aux[n]; memset(aux, 0, n*sizeof(int)); helper(m, 0, aux);}void helper(int dest, int idx, int aux[], int n){ if (dest == 0) dump(aux, n); if (dest <= 0 || idx==n) return; helper(dest, idx+1, aux, n); aux[idx] = 1; helper(dest-idx-1, idx+1, aux, n); aux[idx] = 0;}void dump(int aux[], int n) { for (int i=0; i<n; i++) if (aux) printf(“%3d”,i+1); printf(“\n”);}PS: this is not an elegant implementation,however, it is not necessary to use gray code or other techniques for such aproblem, right?