조합

19 Apr 2023 in Algorithm on Java, Coding, Test

문제

• 문제 내용 없음, 조합을 활용하는 문제일 경우 해결하는 방법

해결방법

• 숫자 N개 중, M개를 뽑는 경우의 수.
• {1,2,3,4} 있을 때, 1뽑고 기준 - 2 - 3 , 1 - 3- 4 처럼 뽑는 방법을 코드로 구현.
• boolean 배열로 점점 depth가 늘어날 때, 방문 여부 표시 해주는 것이 중요.
• m개를 다 뽑고 나면 저장된 boolean배열을 통해 어떤거 뽑았는지 출력.

코드

/**
   * combine 활용, 숫자 N개 중 R개 뽑는 경우의 수
   * 
   * @param arr    뽑고자 하는 배열 리스트
   * @param picked 뽑았는지 체크 하는 boolean 배열
   * @param start  시작 초기 값
   * @param length 배열 길이
   * @param count  뽑고자 하는 숫자의 개수
   */
  public static void combine(int[] arr, boolean[] picked, int start, int length, int count) {
    if (count == 0) {
      for (int i = 0; i < length; i++) {
        if (picked[i]) {
          System.out.print(arr[i] + " ");
        }
      }
      System.out.println("");
    }
    for (int i = start; i < length; i++) {
      picked[i] = true;
      combine(arr, picked, i + 1, length, count - 1);
      picked[i] = false;
    }
  }