[알고리즘] 백트래킹을 활용한 부분 집합 & 순열

[알고리즘] 백트래킹을 활용한 부분 집합 & 순열

백트래킹 부분 집합

/**
 * 
 * powerset 구하기
 *
 */
 
public class powerset_backtrack {
    
    static int[] arr = {3, 5, 8}; // arr 배열의 모든 부분집합을 구해보자
 
    public static void main(String[] args) {
        
        
        boolean[] a = new boolean[arr.length]; // 부분집합에서 원소를 사용할 지 여부를 체크할 배열
        
        backtrack(a, 0, a.length);
        
        
    } // end of main
 
    /** a[] 원소의 사용여부를 체크할 배열, k : 현재의 단계, input : 단계의 끝 범위(고정)*/
    public static void backtrack(boolean[] a, int k, int input) {
        
        boolean[] c = new boolean[a.length];
        
        if (k == input) { // 종료 파트
            process_solution(a, k);// powerset을 출력
        } else { // 재귀 파트
            int ncands = make_candidates(a, k, input, c);// 후보군 만들기
            for (int i = 0; i < ncands; i++) {    
                a[k] = c[i]; // 현재 단계에 후보군 하나를 넣음
                backtrack(a, k+1, input); // 다음단계를 진행하도록 k+1단계를 재귀호출
            }
        }
        
    }    
 
    // end of backtrack()
    
    /** a[] 원소의 사용여부를 체크할 배열, k : 현재의 단계, input : 단계의 끝 범위(고정), c : 후보군을 저장할 배열, return ncands : 후보군 갯수 */
    public static int make_candidates(boolean[] a, int k, int input, boolean[] c) {
        c[0] = true;
        c[1] = false;
        return 2;
    }
    
    /** 완성된 a[] 배열을 보고, 원소를 출력할지 확인해서 powerset을 출력 */
    public static void process_solution(boolean[] a, int k) {
        
        for (int i = 0; i < a.length; i++) {
            if(a[i]) 
                System.out.print(arr[i] + " ");
        }
        System.out.println();
        
        System.out.println("다 출력");
        for (int i = 0; i < a.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        
    }
 
} // end of class

백트래킹 순열

/**
 * 
 * perm 구하기
 *
 */
 
public class perm_backtrack {
    
    static int[] arr = {3, 5, 8}; // arr 배열의 모든 부분집합을 구해보자
 
    public static void main(String[] args) {
        
        
        int[] a = new int[arr.length]; // 부분집합에서 원소를 사용할 지 여부를 체크할 배열
        
        backtrack(a, 0, a.length);
        
        
    } // end of main
 
    /** a[] 원소의 사용여부를 체크할 배열, k : 현재의 단계, input : 단계의 끝 범위(고정)*/
    public static void backtrack(int[] a, int k, int input) {
        
        int[] c = new int[a.length];
        
        if (k == input) { // 종료 파트
            process_solution(a, k);// powerset을 출력
        } else { // 재귀 파트
            int ncands = make_candidates(a, k, input, c);// 후보군 만들기
            for (int i = 0; i < ncands; i++) {    
                a[k] = c[i]; // 현재 단계에 후보군 하나를 넣음
                backtrack(a, k+1, input); // 다음단계를 진행하도록 k+1단계를 재귀호출
            }
        }
        
    }    
 
    // end of backtrack()
    
    /** a[] 원소의 사용여부를 체크할 배열, k : 현재의 단계, input : 단계의 끝 범위(고정), c : 후보군을 저장할 배열, return ncands : 후보군 갯수 */
    public static int make_candidates(int[] a, int k, int input, int[] c) {
        
        boolean[] in_perm = new boolean[a.length+1];
        
        for (int i = 0; i < k; i++) {
            in_perm[a[i]] = true;
        }
        
        int ncands = 0;
        
        for (int i = 1; i <= input; i++) {
            if(!in_perm[i]) {
                c[ncands] = i;
                ncands++;
            }
        }
        
        return ncands;
        
    }
    
    /** 완성된 a[] 배열을 보고, 원소를 출력할지 확인해서 powerset을 출력 */
    public static void process_solution(int[] a, int k) {
        
        for (int i = 0; i < a.length; i++) {
            System.out.print(arr[a[i]-1] + " ");
        }
        System.out.println();
        
    }
 
} // end of class