[재귀, 브루트포스] 순열, 조합, 부분집합

아래의 코드들은 암기해야 한다고 생각할 정도로 숙지하고 있어야 한다.

순열, 조합, 부분집합은 브루트포스(완전탐색)와 매우 연관이 깊다

순열 (Permutation)

순서의 의미가 있다. 선택했던 것을 확인해주는 boolean 타입의 isSelected 배열

package com.ssafy.w0803.p;

import java.util.Arrays;
/**
 * @author THKim
 */
// N개의 서로 다른 수에서 뽑는 순열
public class PermutationTest2 {

	static int N=3,R=2; 
	static int[] input;
	static int[] numbers;
	static boolean[] isSelected;
	
	public static void main(String[] args) {

		input = new int[]{1,4,7};
		numbers = new int[R];
		isSelected = new boolean[N];
	
		permutation(0);
	}
	
	private static void permutation(int cnt) {
		if(cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		// 가능한 모든 수들이 들어있는 배열모든 원소에 대해 시도
		for (int i = 0; i < N; i++) { // i : 인덱스
			if(isSelected[i]) continue; // 인덱스에 해당하는 수가 사용중인 수이면 다음 수로.
			
			numbers[cnt] = input[i];
			isSelected[i] = true;
			
			// 다음 자리순열(cnt+1) 뽑으러 gogo
			permutation(cnt+1);
			isSelected[i] = false;
		}
		
	}
}

 

예) 1 2 3 (N:2)
1  2
1  3
2  1
2  3
3  1
3  2

 

조합 (Combination)

순서의 의미가 없다. startIdx를 저장하여 재귀로 넘겨줘서 startIdx부터 시작 (중복되지 않기 위해)

package com.ssafy.w0803.c;

import java.util.Arrays;
/**
 * @author THKim
 */
// N개의 서로 다른 수 R개 뽑는 조합
public class CombinationTest {

	static int N=3,R=2; 
	static int[] input;
	static int[] numbers;
	
	public static void main(String[] args) {

		input = new int[]{1,4,7};
		numbers = new int[R];
	
		combination(0,0);
	}
	
	private static void combination(int cnt,int start) {
		if(cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		// start 위치의 수부터 가능한 수 모두 고려
		for (int i = start; i < N; i++) { // i : 인덱스
			numbers[cnt] = input[i];
			// 다음 자리순열 뽑으로 gogo
			combination(cnt+1,i+1);
		}
		
	}

}

예) 1 2 3  (N:2)
1  2
1  3
2  3

 

부분 집합 (Subset)

count 해주는 변수가 필요하다

package com.ssafy.algo.w0804;

import java.util.Arrays;

public class E01_PerCombiTest {
	static int [] num = {1,2,3};
	static int N =2; 
	static int sCount = 0;
    
	//부분집합
	private static void powerSet(int cnt, boolean[] isSelected) {
		if(cnt==N) {
			sCount++;
			System.out.print("{");
			for(int i =0;i<N;i++) {
				if(isSelected[i])
					System.out.print(num[i]+" ");
			}
			System.out.print("},");
			return;
		}
		//선택
		isSelected[cnt]=true;
		powerSet(cnt+1, isSelected);
		
		//비선택
		isSelected[cnt]=false;
		powerSet(cnt+1, isSelected);
	}
	
	public static void main(String[] args) {
		
//      3. num으로 구성할 수 있는 모든 부분집합을 출력하시오.   
		System.out.println("---부분집합---");
		powerSet(0, new boolean[N]);
		System.out.println("\n총경우의수:"+sCount);
		
	}

}