[LeetCode] 77. Combinations

문제풀이

1부터 n까지의 길이에서 k개의 숫자의 모든 조합을 구하는 문제이다.

n개의 숫자를 사용해서 길이가 k인 combination 생성

• seq[i]는 seq[i-1]보다 커야 한다
• [seq[i-1]+1, n] 사이의 숫자 중에서 seq[i]를 선택한다.

우선 n개의 숫자 중에서 k개의 숫자를 선택하는 함수를 작성하면 다음과 같다.

void choose(int n, int k, int count)
{
    if(count==k)
    {
        return;
    }

    int prev = count>0 ? comb[count-1] : 0;
    for(int i=prev+1;i<=n;i++)
    {
        comb[count] = i;
        choose(n, k, count+1);
    }
}

이 문제가 까다로운 이유는 모든 조합의 경우의 수를 2D array에 저장해야 하기 때문이다.

이 문제에서 row의 개수는 nCk, column의 개수는 k이다.

우선, row의 개수를 구하는 함수를 작성하면 아래와 같다.

void numberofrows(int n, int k)
{
    if(k==0 || n==k) return 1;
    return numberofrows(n-1, k) + numberofrows(n-1, k-1);
}

2D array로 반환하기 위해서는 다음의 3가지를 결정해야 한다.

• array를 가리키는 pointer(int**)
• row의 개수(int)
  • returnSize가 가리키는 변수에 저장해야 한다.
• column의 개수(int*)
  • returnColumnSizes가 가리키는 변수에 저장해야 한다.

이를 반영하여 코드를 작성하면 아래와 같다.

/**
 * 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().
 */
 
int **array, num_comb=0;
int comb[21];

int numberofrows(int n, int k)
{
    if(k==0 || n==k) return 1;
    return numberofrows(n-1, k) + numberofrows(n-1, k-1);
}

void choose(int n, int k, int count)
{
    if(count==k)
    {
        for(int j=0;j<k;j++)
        {
            array[num_comb][j]=comb[j];
        }
        num_comb+=1;
        return;
    }

    int prev = count>0 ? comb[count-1] : 0;
    for(int i=prev+1;i<=n;i++)
    {
        comb[count] = i;
        choose(n, k, count+1);
    }
}


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

	//row의 개수
    int numofrows = numberofrows(n, k);
    *returnSize = numofrows;
	
    //colum의 개수
    *returnColumnSizes = (int*) malloc(sizeof(int)*numofrows);
    for(int i=0;i<numofrows;i++)
    {
        (*returnColumnSizes)[i]=k;
    }

    array = (int**) malloc(sizeof(int*)*numofrows);
    for(int i=0;i<numofrows;i++)
    {
        array[i]=(int*)malloc(sizeof(int)*k);
    }

    num_comb=0;
    choose(n, k, 0);

    return array;
}