[디폴트코드] 부분집합/순열/조합

• 손이 기억해야할 디폴트 코드들
• 순열, 조합, 부분집합

재귀 순열

• 방문체크를 하고 재귀한다음 체크 초기화 하는 것이다.
• 항상 for문을 돌려서 처음 부터

import java.util.Arrays;
public class 재귀순열 {
	static int cnt = 0;
	static int[] N = {1,2,3,4,5};
	static int[] R = new int[3];
	static boolean[] select = new boolean[N.length];
	
	public static void main(String[] args) {
		perm(0);
		System.out.println(cnt);
	}

	static void perm(int R_index) {
		if (R_index == R.length) {
			System.out.println(Arrays.toString(R));
			cnt++;
			return;
		}
		
		for (int i = 0; i < N.length; i++) {
			if (select[i])
				continue;
			R[R_index] = N[i];
			select[i] = true;
			perm(R_index+1);
			select[i] = false;
		}
	}
}

재귀 조합

• 인덱스를 주고, 이번 경우를 넣는 상황과 안 넣는 상황을 재귀하기.

import java.util.Arrays;

public class 재귀조합 {
	static int count = 0;
	static int[] N = {1,2,3,4,5};
	static int[] R = new int[3];
	
	public static void main(String[] args) {
		combination(0,0);
		System.out.println("개수 : " + count);
	}
	
	static void combination(int N_index , int R_index) {
		if ( R_index == R.length ) {
			System.out.println(Arrays.toString(R));
			count++;
			return;
		}
		if(N_index == N.length)
			return;
		R[R_index] = N[N_index];
		combination(N_index + 1, R_index+1);
		combination(N_index + 1, R_index);
	}
}

재귀 부분집합

package CopyCode;

public class 재귀부분집합 {
	static int cnt = 0;
	static int[] N = {1,2,3,4,5};
	static boolean[] select = new boolean[N.length];
	
	public static void main(String[] args) {
		subset(0);
		System.out.println(cnt);
	}
	
	static void subset(int N_index) {
		if (N_index == N.length) {
			printSubset();
			cnt += 1;
			return;
		}
		
		select[N_index] = true;
		subset(N_index + 1);
		
		select[N_index] = false;
		subset(N_index + 1);
		
	}
	
	static void printSubset() {
		System.out.print("<< ");
		for (int i = 0; i < N.length; i++) {
			if(select[i] == true)
				System.out.print( N[i] + " ");
		}
		System.out.println(">>");
	}

}