조합구하기

코드

import java.util.*;
class 조합구하기{
	static int[] combi;
	static int n, m;
	
	static void DFS(int L, int s) {
		if(L==m) {//L이 m과 같다면 목표 배열 크기까지 수행 후 다시 호출된 것
			//즉, L은 배열인덱스범위 밖이다.
			System.out.println(Arrays.toString(combi));
			return;
		}
		for (int i = s; i <= n; i++) {
			combi[L] = i;
			DFS(L+1, i+1);
		}
	}
	
	
	public static void main(String[] args){
		n=5; // 최대 숫자
		m=2; // 조합배열 크기
		combi=new int[m];//조합 배열
		DFS(0, 1);//배열인덱스, 시작 숫자
	}
}

---

결과

[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]

---

상태값 변화 예측

검증 코드

import java.util.*;
class 조합구하기{
	static int[] combi;
	static int n, m, cnt;
	
	static void DFS(int L, int s) {
		if(L==m) {//L이 m과 같다면 목표 배열 크기까지 수행 후 다시 호출된 것
			//즉, L은 배열인덱스범위 밖이다.
			cnt++;
			System.out.println(cnt+" "+"L"+L+" "+Arrays.toString(combi) +"[출력]");
			return;
		}
		for (int i = s; i <= n; i++) {
			cnt++;
			combi[L] = i;
			System.out.println(cnt+" "+"L"+L+" "+Arrays.toString(combi));
			DFS(L+1, i+1);
		}
	}
	
	
	public static void main(String[] args){
		n=5; // 최대 숫자
		m=2; // 조합배열 크기
		combi=new int[m];//조합 배열
		DFS(0, 1);//배열인덱스, 시작 숫자
	}
}

---

결과

1 L0 [1, 0]
2 L1 [1, 2]
3 L2 [1, 2][출력]
4 L1 [1, 3]
5 L2 [1, 3][출력]
6 L1 [1, 4]
7 L2 [1, 4][출력]
8 L1 [1, 5]
9 L2 [1, 5][출력]
10 L0 [2, 5]
11 L1 [2, 3]
12 L2 [2, 3][출력]
13 L1 [2, 4]
14 L2 [2, 4][출력]
15 L1 [2, 5]
16 L2 [2, 5][출력]
17 L0 [3, 5]
18 L1 [3, 4]
19 L2 [3, 4][출력]
20 L1 [3, 5]
21 L2 [3, 5][출력]
22 L0 [4, 5]
23 L1 [4, 5]
24 L2 [4, 5][출력]
25 L0 [5, 5]

---