題目
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[[2,4], [3,4], [2,3],[1,2], [1,3],[1,4],]
分析
基本的組合問題十籍，可以使用遞歸或回溯等算法础浮。
我使用的是遞增赖欣，比如12-13-14-23-24-34轧坎，從后面依次遞增到最大的n客税，如果到達(dá)最大，就找到之前的一位增加而晒，這時(shí)之后的數(shù)字需要依次遞增略步。例如145-234
此處需要帶上型號(hào)，否則 (*columnSizes)[i]=k;就會(huì)報(bào)錯(cuò)会傲，內(nèi)存對(duì)齊問題锅棕，找這個(gè)bug找了好久才找到。淌山。裸燎。
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** combine(int n, int k, int** columnSizes, int* returnSize) {
int n1=n,k1=k;
if(n1<k1*2)k1=n-k1;
int temp1=1,temp2=1;
while(k1>=1)
{
temp1=temp1*n1;
n1--;
temp2=temp2*k1;
k1--;
}
*returnSize=temp1/temp2;
int ** ans=(int**)malloc(sizeof(int *)*(*returnSize));
*columnSizes=(int *)malloc(sizeof(int)*(*returnSize));
for(int i=0;i<(*returnSize);i++)
{
ans[i]=(int *)malloc(sizeof(int)*k);
for(int j=0;j<k;j++)
ans[i][j]=0;
(*columnSizes)[i]=k;
}
for(int i=0;i<k;i++)
{
ans[0][i]=i+1;
}
for(int i=0;i<(*returnSize)-1;i++)
{
for(int j=0;j<k;j++)
ans[i+1][j]=ans[i][j];
int p=k-1;
while(ans[i+1][p]>=n+p-k+1&&p>=0)
p--;
if(p==k-1)
{
ans[i+1][p]=ans[i+1][p]+1;
}
else if(p>=0)
{
ans[i+1][p]=ans[i+1][p]+1;
for(int j=p+1;j<k;j++)
ans[i+1][j]=ans[i+1][j-1]+1;
}
}/**/
return ans;
}
