알고리즘 - 조합

- 재귀를 활용한 조합 구현1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 조합_재귀 {

	static String[] items = {"A", "B", "C", "D"};
	static int N = items.length;
	static int R = 2; // 몇개의 원소를 고를 것인가
	
	static String[] sel = new String[R]; //내가 선택한 원소
	
	static List<String[]> list = new ArrayList<>();
	
	public static void main(String[] args) {
		combination(0, 0);
		
		for(String[] strs : list) {
			System.out.println(Arrays.toString(strs));
		}
		
		
	}
	//idx 	: 내가 이번 깊이에서 고려할 원소의 index
	//sidx  : 현재 뽑을 자리 (결과값에 들어간 자리)
	public static void combination(int idx, int sidx) {
		//base case
		if(sidx == R) {//다 뽑았어
//			System.out.println(Arrays.toString(sel));
			list.add(sel);
			return;
		}
		//recursive case
		//경계값 결정
        //중복을 허용하지 않기 때문에, 이전에 확인한 위치의 다음부터 본다.
        //또한 N개 중 R개를 뽑을 건데, 
        //N개의 원소들 중 남은 개수가 R-sIdx(뽑아야할 수의 개수에서 현재 뽑은 개수를 뺀 값, 즉 앞으로 뽑을 개수)
        //보다 적으면 끝까지 다 뽑을 수 없으므로 i가 그 범위 내에 있도록 제한해야 한다.
        //N-(남은개수)가 현재 상태에서 고려할 수 있는 배열의 마지막 index이다.
		for(int i = idx ; i<= N-R+sidx; i++) {
			sel[sidx] = items[i];
			combination(i+1, sidx+1);
		}
	}
	
}

 

- 재귀를 활용한 조합 구현(2) 

import java.util.Arrays;

public class 조합_재귀2 {
	static String[] items = {"A", "B", "C", "D"};
	static int N = items.length;
	static int R = 2; // 문제에서 제시할 뽑아야할 원소 개수
	
	static String[] sel = new String[R]; //내가 선택한 원소
	
	public static void main(String[] args) {
		combination(0, 0);
		
	}
	//idx 	: 내가 이번 깊이에서 고려할 원소
	//sidx  : 현재 뽑을 자리 
	public static void combination(int idx, int sidx) {
		//base case
		if(sidx == R) {//다 뽑았을 때 다 뽑은 배열 출력하고 메서드 종료
			System.out.println(Arrays.toString(sel));
			return;
		}
		if(idx == N) { //고려 다했어. 더 볼 필요가 없다.
			return;
		}
		//recursive case
		sel[sidx] = items[idx]; //sidx 자리에 현재 보고있는 idx 토핑을 저장할래
		combination(idx+1, sidx+1); //이번 재료 썼고, 다음재료 판단하러가보자.
		combination(idx+1, sidx);   //이번 재료 안썼고, 다음재료 판단하러가보자.
		
	}
	
}