[backtracking] combination,permutation,subset

순열, 조합, 부분 집합

순열

N개의 원소에서 순서를 생각하며 R개의 원소를 선택하는 방법

입력 : [1, 2, 3]
출력 : [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]

• visited를 활용하여 구현한다.

조합

N개의 원소에서 R개의 원소를 선택하지만, 뽑는 순서는 고려하지 않는다.

입력 : [1, 2, 3]
출력 : [1, 2], [1, 3], [2, 3]

• 인데스의 매개변수를 이용해 구현한다.

부분 집합

조합에서 선택하는 수가 0 ~ n개 일 경우

입력 : [1, 2, 3]
출력 : [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

• 비트마스킹을 활용해서 구할 수도 있다.