[알고리즘]n개의 원소에서 m개를 고르는 모든 조합 찾기.

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘.

// n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘.

/*
예를 들어 N이 7이면 (0, 1,2, 3), (0, 1, 2, 4), (0,1, 2, 5), ....(3, 4, 5, 6).. 이다.

만약 m이 5개면? for문 5번해야함;; 뭔짓임.
*/

void UseFor(int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			for (int k = j + 1; k < n; k++)
			{
				for (int l = k + 1; l < n; l++)
				{
					cout << i << " " << j << " " << k << " " << l << endl;
				}
			}
		}
	}
}

/*
n: 전체 원소의 수
picked : 지금까지 고른 원소들의 번호
toPick : 더 고를 원소의 수
*/
void pick(int n, vector& picked, int toPick)
{
	if (toPick == 0)
	{
		for (int nIndex = 0; nIndex < picked.size(); ++nIndex)
		{
			cout << picked[nIndex] << " ";
		}

		cout << endl;
		return;
	}

	// 고를 수 있는 가장 작은 번호를 계산한다.
	int smallest = picked.empty() ? 0 : picked.back() + 1; 

	// 이 단계에서 원소 하나를 고른다.
	for (int next = smallest; next < n; ++next)
	{
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}
}

int main()
{
	int n = 10;

	//UseFor(n);

	vector v;
	pick(n, v, 8);

	getchar();

	return 0;
}

[ 결과 ]