순열과 조합

1)순열

import java.util.*;
public class Main {
	public static void solution(char []item, char []bucket, int k) {

	        if( k == 0 ) { //다 뽑았으면 출력
	            for(int i=0; i<bucket.length; i++ ) { 
	                System.out.print( bucket[i] + " " );
	            }
	            System.out.println();
	            return;
	        }

	        int lastIndex = bucket.length - k - 1; //현재 bucket에 들어있는 원소의 개수 - 1
	        for(int i=0; i<item.length; i++ ) {
	            int flag = 0;
	            for(int j=0; j<=lastIndex; j++) {
	                if( item[i] == bucket[j] ) { //이미 버켓에 들어있으면 뽑지 않음
	                    flag = 1;
	                    break;
	                }
	            }
	            if( flag == 1 ) continue;
	            bucket[lastIndex+1] = item[i];//마지막으로 담은 인덱스 다음에 새로운 원소 추가
	            solution(item,bucket,k-1); 
	        }
	    }

	    public static void main(String[] args) {
	        char []item = { 'a', 'b', 'c', 'd', 'e' };
	        char []bucket = new char[item.length];

	        solution( item, bucket, item.length);
	    }
}

시간복잡도: O(n!)

 

 

 

 

2) 조합

백트래킹을 이용하는 방법과 재귀를 이용하는 방법이 있음

현재 원소를 뽑는 경우 + 현재 원소를 뽑지 않는 경우

import java.util.*;
public class Main {

//백트래킹을 이용한 방법
	static void comb1(char[] arr, boolean[] picked, int start, int n, int r) {
		if(r == 0) {
			print(arr, picked, n);
			return;
		} 

		for(int i=start; i<n; i++) {
			picked[i] = true;
			comb1(arr, picked, i + 1, n, r - 1);
			picked[i] = false;
		}
	}
    
    
//재귀를 이용한 방법	
     static void comb2(char[] arr, boolean[] picked, int depth, int n, int r) {
	        if (r == 0) {
	            print(arr, picked, n);
	            return;
	        }
	        
	        if (depth == n) {
	            return;
	        }

	        picked[depth] = true;
	        comb(arr, picked, depth + 1, n, r - 1);

	        picked[depth] = false;
	        comb(arr, picked, depth + 1, n, r);
	    }
    
	public static void print(char[] arr, boolean[] picked, int n) {
		for(int i=0; i<n; i++)
			if(visited[i])
				System.out.print(arr[i]);
		System.out.println();
	}
    
	public static void main(String[] args) {
		char []item = { 'a', 'b', 'c' };
		boolean []pick = new boolean[item.length];

		combination(item, pick, 0, 3, 2);
		com(item, pick, 0, 3, 2);
    }
}

시간복잡도: O(2^n)