중복조합

[백트래킹] 조합, 순열, 중복조합, 중복순열 (재귀이용)

목차 조합 순열 중복조합 중복순열 들어가며 백준에서 백트래킹 문제를 풀 때, 문제보고 대충 이런 식이면 되겠지 하고 문제들을 풀다 보니 헷갈리는 부분이 있었습니다. 그동안 머릿속에 정리된 내용 없이 중구난방으로 문제를 풀었는데, 정리된 내용이 없나 하고 찾아보다가 얍문님의 블로그 포스팅을 보고 이거다 싶어서 하나로 정리해두려고 합니다. 조합 조합이란? 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 의미합니다. 가장 중요한 것은 순서가 상관없다는 점입니다. 예를 들어 {1, 2, 3, 4, 5}로 이루어진 집합이 있을 때, 3개를 선택한다고 해봅시다. 이때 {1, 2, 3}과 {3, 2, 1}은 같은 부분집합입니다. 즉, {1, 2, 3} , {1, 2, 4},..