C# 알고리즘 - Combination

public void CombinationIterWithBitMask()
{
    int[] nums = { 1, 2, 3 };
    int n = nums.Length;
    List<List<int>> result = new List<List<int>>();

    for (int i = 0; i < (1 << n); i++)
    {
        List<int> combination = new List<int>();
        for (int j = 0; j < n; j++)
        {
            // i의 j번째 비트가 1인 경우 nums[j]를 조합에 추가
            if ((i & (1 << j)) != 0)
            {
                combination.Add(nums[j]);
            }
        }
        result.Add(combination);
    }

}

Combination을 이용하는 문제를 풀다보니 문득 어떤 방식들이 있을지 고민해보다 찾은 방식들을 소개해 본다.

1. 재귀

대부분의 사람들에게 익숙한 재귀 코드로 nums라는 리스트에서 pickUpNumber개의 요소를 List로 반환해 주는 코드이다

public List<List<int>> Combine(int[] nums, int pickUpNumber)
{
    List<List<int>> result = new List<List<int>>();
    CombineRecursive(nums, pickUpNumber, 0, new List<int>(), result);
    return result;
}
public void CombineRecursive(int[] nums, int pickUpNumber, int start, List<int> curNums, List<List<int>> result)
{
    if (pickUpNumber == 0)
    {
        result.Add(new List<int>(curNums));
        return;
    }
    for (int i = start; i < nums.Length; i++)
    {
        curNums.Add(nums[i]);
        CombineRecursive(nums, pickUpNumber - 1, i + 1, curNums, result);
        curNums.RemoveAt(curNums.Count - 1);
    }
}

 

2. 단순 반복

 

이 방식은 위 방식에 비해 StackOverFlow를 미리 방지할 수 있다는 장점이 있다

마찬가지로 PickUpNumber가 고르고 싶은 개수 length는 숫자의 길이다

위 방식과 다르게 인덱스를 return하는 방식으로 구현하였다

 

public List<List<int>> CombinationIter(int length, int pickUpNumber)
{
    List<List<int>> result = new List<List<int>>();
    int[] temp = new int[pickUpNumber];
    int i = 0;
    while (i >= 0)
    {
        temp[i]++;
        if (temp[i] >= length) i--;
        else if (i == pickUpNumber - 1)
        {
            List<int> templist = new List<int>();
            for (int j = 0; j < pickUpNumber; j++) templist.Add(temp[j]);
            result.Add(templist);
        }
        else
        {
            i++;
            temp[i] = temp[i - 1];
        }
    }
    return result;
}

 

2. 비트연산자

이 방식은 비트 연산자를 이용한 방식으로 좀더 빠르게 단순 비교문보다 좀더 빠르게 작동하는 방식이다

단점으로는 현재 모든 조합의 경우를 출력하는데 아직 하나하나 출력하는 방법은 구상하지 못했다는 점이다