★★★조합 구하기(DFS)

n개 중에 m개 뽑는것. 배열을 m 크기 만큼 만들어야한다.

for문의 의미는 s 부터 n or n-1 까지 조합을 뽑아내겠다는 의미이다.

s = 1, n = 4 이면 1 부터 4 까지의 조합을 만들어냄(for문을 i <= n까지 돌렸을 때)

s = 0, n = 4 이면 0 부터 3 까지의 조합을 만들어냄(for문을 i < n까지 돌렸을 때)

 

import java.util.*;

public class Main {
    static int[] combi;
    static int n, m;

    public void DFS(int L, int s){
        if(L == m) {
            for(int x : combi) System.out.print(x + " ");
            System.out.println();
        }
        else {
            //조합은 외워버리기
            for(int i = s; i <= n; i++) {
                combi[L] = i;
                DFS(L+1, i+1);
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        combi = new int[m];
        T.DFS(0, 1);
    }
}

조합, 순열의 제일 큰 차이는 i의 시작 지점이다.

순열은 배열의 값을 이용하면 L의 시작 값은 0, 0부터 n-1까지

해당 자체의 숫자를 뽑는거면 L의 시작 값은 1, 1부터 n까지 돌리면 된다.

 

조합은 무조건 s로만 시작하고 배열의 값을 이용하면 s의 시작값은 0, s부터 n-1까지

숫자를 뽑는거면 s의 시작값은 1, s부터 n-1까지 돌리면된다.

웬만하면 0부터 n개 이전 까지 뽑는 문제가 많을 것 같다.

 

for(int i = 0; i < n; i++) {
  pm[L] = arr[i];
  dfs(L+1);
}

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

 

중복조합은 i+1 부분을 i로만 바꿔주면 되겠다.