[77] Combinations

哎啊！！！靠自己寫出來了啊啊啊啊啊啊（噴淚）

但這時間這麼慢是怎麼回事

說要一千多ms，別人只要五十幾ms ?!

結果貼過來跑也要一千多ms啊！！！！！！

騙我逆！！！

是不是你們以前寫的時候測資比較少！！！是不是這樣 XD

不管啦不管啦我要貼我自己的版本

寫到眼淚都要流出來了

大意就是先把這個return的size算出來，所也會有 size x k 的矩陣

然後再下去跑recursive 把每個位置該填的值填進去，

最後卡住的地方是，除了k=1 的最後一次return 之外，外層的return 也需要填值，

而行數(x)在迴圈裡一路增加，這樣會爆掉，要記得把原始的x 記下來，

最後return 的長度是 最後的index 減掉一開始的x，才是這次它所新增的長度。

（還是看不懂的話只好用 n=5 k=3 的例子畫圖填表了>< )

/**

* Return an array of arrays of size *returnSize.

* The sizes of the arrays are returned as *returnColumnSizes array.

* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().

*/

long factorial (int n)

{

if (n == 1 || n==0)

return 1;

return n* factorial(n-1);

}

int running(int n, int k, int start, int end , int **ret, int x, int y)

{

if (k==1)

{

int retCount=0;

for (int i=start ; i<= end;i++)

{

ret[x++][y]=i;

retCount++;

}

return retCount;

}

int count = x;

for (int i=start; i<= (end-k+1);i++)

{

int tmpCount=0;

tmpCount=running(n,k-1,i+1,end,ret,x,y+1);

for (int j=0;j<tmpCount;j++)

ret[x+j][y]=i;

x+=tmpCount;

}

return (x-count);

}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){

long size = factorial(n) / ( factorial(k) *factorial(n-k));

int **ret= malloc (sizeof(int*)*size);

*returnColumnSizes = malloc (sizeof (int)* size);

*returnSize = size;

for (int i=0;i<size; i++)

{

ret[i]= calloc(k,sizeof(int));

(*returnColumnSizes)[i]=k;

}

running(n,k,1,n,ret,0,0);

return ret;

}

#if 0

1,2,3 k=2

1=> 2,3 k=1

0(1,2)

1(1,3)

2=> 3 k=1

2(2,3)

1,2,3,4,5 k=3

1 => 2,3,4,5 k=2 => 2=> 3,4,5 k=1

(1,2,3)(1,2,4)(1,2,5)

(1,3,4)(1,3,5)

(1,4,5)

2 => 3,4,5 k=2 => 3=> 4,5 k=1

(2,3,4)(2,3,5)

(2,4,5)

3=> 4,5 k=2 => 4=> k=1

(3,4,5)

#endif