# 2. 재귀

### 4. 멱집합

* {1,2,3,4} 모든 부분집합
  * 1을 포함하지 않는 모든 부분집합
  * 1을 포함하는 모든 부분집합
  * 위 2개 재귀

```java
  public void powerSet(int[] P, int[] S) {
    if (S.length == 0) {
      System.out.println(Arrays.toString(P));
    } else {
      int t = S[0];
      int[] ints = Arrays.copyOf(P, P.length + 1);
      ints[ints.length - 1] = t;

      powerSet(P, Arrays.copyOfRange(S,1, S.length));             // t를 포함하지 않은 집합 모두 출력
      powerSet(ints, Arrays.copyOfRange(S,1, S.length));     // t를 반드시 포함하는 부분 집합들
    }
  }
```

* 상태공간트리 활용
  * k = 트리 레벨 (위치, 노드 깊이)
    * ex) k=2 -> 2번째 위치 값까지 포함 여부에 대한 집합 
  * k == 집합 길이 -> 모든 집합 (마지막 리프노드)

```java
  private char data[] = {'a', 'b', 'c', 'd'};
  private int n = data.length;
  private boolean[] include = new boolean[n];
  
  // k-> 트리상 현재 나의 위치 표현
  public void powerSet2(int k) {
    if (k == n) { // 내 위치가 리프노드 라면
      for (int i = 0; i < n; i++) {
        if (include[i]) {
          System.out.print(data[i] + " ");
        }
      }
      System.out.println();
      return;
    }

    // 왼쪽 (포함하지 않는)
    include[k] = false;
    powerSet2(k + 1);
     
    // 오른쪽 (포함하는)
    include[k] = true;
    powerSet2(k + 1);
  }
```

### 5. 순열

* data = {1,2,3,4} -> 4! = 24 (1234의 모든순열 가지수)
  * 1234, 1243 ... 4321
  * 1 -> 234 의 모든 순열
    * 12 -> 34 의 모든 순열
    * 13 -> 24 의 모든 순열
    * 14 -> 23 의 모든 순열
      * 하위 반
  * 2 -> 134 의 모든 순열
  * 3 -> 124 의 모든 순열
  * 4 -> 123 의 모든 순열
* 상태공간트리
* 멱집합(조합, 순서 상관x) 과 순열(순서상관) 나열의 응용
  * 배낭문제(Knapsack)
    * 무게와 가격이 정해진 N개의 아이템과 용량이 W인 배낭이 있다. 배낭의 용량을 초과하지 않으면서 가격의 합이 최대가 되도록 아이템을 배낭에 넣으려면?? &#x20;
    * 시간복잡도 : O(2^n)..... 최적화 필요&#x20;
    * 멱집합 -> 무게 > W 무시하고, W<= 무게 필터링 -> 최대인거 구하기&#x20;
  * TSP&#x20;
    * 모든 도시 출장 -> 원점 복귀 -> 가장 짧은 투어 경로 구하기