알고리즘 공부(재귀를 이용한 순열과 조합)

요즘 읽는 책의 내용에서 어떠한 것을 알기 위해서는 그것을 단순히 공부하는 방법도 있지만 차이가 나는 두가지의 비교를 통해 그것에 대한 이해를 높이는 방법이 있다고 들었다. 그래서 재귀를 이용한 순열과 조합의 차이에 대해서 이해하려고 한다.  우선 순열과 조합의 차이는 같은 원소를 사용했을때 순서를 인정하여 원소의 순서가 다르면 다른것이라고 인정하면 순열 순서가 달라도 원소가 같으면 같은것이라고 순서를 무시하면 조합이라는 정의를 기억하며 재귀를 호출할때 for문의 이용하는 방법이 다르다  순열은 아래의 코드 처럼 따로 체크배열을 두어서 재귀를 호출할때 사용한 원소만 사용하지 않게 하고 원소전체에 대해서 재귀를 돌린다. 하지만 반대로 

 

void dfs(int s, int L){

for(int i=1; i<=n; i++){
    if(ch[i]==0){
         res[L]=a[i];
         ch[i]=1;
        dfs(L+1);
         ch[i]=0;
      }
   }

}

 

조합의 경우는 사용한 원소의 범위 자체를 제한하여 (for문의 범위를 제한)하여 재귀를 호출한다. 

 

void dfs(int s, int L){

    for(i=s; i<n; i++){
          ch[L]=i;
         dfs(i+1, L+1);
    }

}

 

그래서 순열은 {1234}의 원소에 대해서 조합시 {132}의 결과값이 나오는데 반해 조합은 이러한 결과값이 나오지 않는다 ({123}으로 이미 값이 나오기 때문이다.)