Java - Combination

조합

• n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우이다.
• 순열에서 중복 제거한 것과 같다.

[1, 2, 3] 배열에서. 2개의 수를 순서 없이 뽑으면 다음과 같다.

[1, 2]

[1, 3]

[2, 3]

• 순열과 달리 조합은 r 을 유지할 필요 없이 숫자를 하나 뽑을 때마다 r을 하나씩 줄여준다.

• r==0 일 때 r 개의 숫자를 뽑은 경우이다.

백트래킹으로 구현

• 코드

  /**
   * @param arr     배열
   * @param visited 방문한 노드
   * @param start   시작할 노드
   * @param n       배열의 길이
   * @param r       조합의 길이
   */
  static void com1(int[] arr, boolean[] visited, int start, int n, int r) {
    // 
    if (r == 0) {
      print(arr, visited, n);
      return;
    }

    for (int i = start; i < n; i++) {
      visited[i] = true;
      com1(arr, visited, i + 1, n, r - 1);
      visited[i] = false;
    }
  }

• start 변수를 기준으로 탐색을 시작한다.
  start가 0으로 시작해 for문을 돌면서 방문 후 뽑은 노드는 true 표시를 하고 뽑지 않으면 다시 false로 둔다.

• 1, 3을 뽑았을 때 [true, false, true, false] 임을 확인할 수 있다.