[JAVA] 재귀함수 및 순열 예시

재귀함수 예시

public class C1207RecurCombiPermu {
    public static void main(String[] args) {
        List<Integer> myList = new ArrayList<>(Arrays.asList(1, 2, 3, 4)); //1,2,3,4
        List<List<Integer>> combination_list = new ArrayList<>();
        List<Integer> temp = new ArrayList<>(); // temp의 주소
        combination(2, 0, temp, combination_list, myList);
        System.out.println(combination_list);
    }
    
    static void combination(int n, int start, List<Integer> temp, List<List<Integer>> combination_list, List<Integer> myList){
        if (temp.size() == n) { // 종료조건 temp.size가 2일때 combination_list에 add하고 종료
            combination_list.add(new ArrayList<>(temp)); //1,2   1,3   1,4
            return;
        }
        
        for (int i = start ; i < myList.size(); i++) { // int i 값을 0으로 두면 변화하지 않기 때문에 값이 전체가 다 나온다.
//            그렇기 때문에 int i 값을 start변수로 두고 combination에 start값을 i+1로 해주어야 중복이 되지않고 1,2 1,3 1,4 2,3 2,4 3,4 이렇게 나온다.
            temp.add(myList.get(i));
            combination(n, i+1, temp, combination_list, myList); // 메서드 호출이기때문에 변수명으로 넣어야 한다.
            temp.remove(temp.size() - 1);
        }
    }
}
// 결과값 : [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

 

 

순열 예시

public class C1207RecurCombiPermu {
    public static void main(String[] args) {
        List<Integer> myList = new ArrayList<>(Arrays.asList(1, 2, 3, 4)); //1,2,3,4
        List<List<Integer>> permutation_list = new ArrayList<>();
        List<Integer> temp = new ArrayList<>(); // temp의 주소
        boolean[] visited = new boolean[myList.size()];
        permutation(2, temp, permutation_list, myList, visited);
        System.out.println(permutation_list);
    }

    static void permutation(int n, List<Integer> temp, List<List<Integer>> permutation_list, List<Integer> myList, boolean[] visited){
        if(temp.size()==n){
            permutation_list.add(new ArrayList<>(temp));
            return;
        }
        
        for (int i = 0 ; i < myList.size(); i++) { // int i 값을 0으로 두면 변화하지 않기 때문에 값이 전체가 다 나온다.
            if(visited[i] == false){ // i번째 visited가 false 일때 temp add 로직 추가
                visited[i] = true; // i번째 visited를 true로 변경
                temp.add(myList.get(i)); // temp 배열에 add
                permutation(n, temp, permutation_list, myList, visited); // 메서드 호출이기때문에 변수명으로 넣어야 한다.

                temp.remove(temp.size() - 1); // 백트랙킹// index 1번째 요소값 삭제
                visited[i] = false; // i번째 visited를 false로 변경
            }
        }
    }
}
// 결과값 : [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]