출처

https://bcp0109.tistory.com/15?category=848939
너무 간단하고 핵심을 잘 짚어준 블로그라 많이 참고하였습니다.

---

Permutation

static void permutation(int[] 배열, int 깊이, int n, int r){
	if(depth == r){ //종료 조건, depth가 r개만큼 다 찼으면
    	print(arr,r);
        return;
    }
    
    for(int i = 깊이; i < n; i++){ //대장 자리
    	swap(배열, 깊이, i); // 바꿈
        permutation(배열,깊이+1,n,r); //재귀
        swap(배열, 깊이, i); // 원상 복귀
    }
}

static void swap(int[] 배열, int 깊이, int i){
        int temp = 배열[i];
        배열[i] = 배열[깊이];
        배열[깊이] = temp;
    }

• nPr : n개중에 r개를 순서에 따라 다르게 뽑습니다. 즉 1,2,3과 3,1,2는 원소가 같지만 순서가 다르므로 다른 부분집합으로 인식됩니다.

permutation은 depth를 +1씩 해가면서r개와 동일할 때 까지 swap을 하며 재귀로 구합니다.

---

Combination

public void combination(int[] 배열, boolean[] 방문, int 시작, int n, int r){
	if(r == 0){ //종료 조건, 더 이상 선택할 요소가 없으면 끝
    	print(배열,방문,n);
        return;
    }
    
    for(int i = 시작; i < n; i++){
    	방문[i] = true;
    	combination(배열,방문,i+1,n,r-1);
        방문[i] = false;
    }
}

• nCr : n개 중에서 r개를 순서에 상관 없이 뽑습니다. 즉 1,2,3과 3,1,2는 같은 부분집합으로 인식 됩니다.

Combination은 i를 +1 하고 동시에 r을 -1을 합니다. r이 0이 될때까지 방문을 체크하며 재귀로 구합니다.

---

요약

순열과 조합 모두 재귀를 이용하여 구할 수 있습니다.
순열은 방문을 +1 씩 해가며 방문 == r까지 swap을 이용하며
조합은 i를 +1, r을 -1 씩 해가며 r == 0까지 방문을 체크합니다.