[알고리즘] Leetcode_77_Combinations 조합

Problem

Solve

class Solution {
    public List<List<Integer>> answer = new ArrayList<>();
    public List<Integer> list = new ArrayList<>();

    public void combination(int[] arr, boolean[] visited, int start, int depth, int k){
        if(depth == k){
            for(int i = 0 ; i < arr.length; i++){
                if(visited[i]) list.add(arr[i]);
            }
            answer.add(list);
            list = new ArrayList<>();
            return;
        }

        for(int i = start ; i < arr.length ; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, depth+1, k);
                visited[i] = false;
            }
        }

    }
    public List<List<Integer>> combine(int n, int k) {
        int[] arr = new int[n];
        for(int i = 0 ; i < n ; i++) arr[i] = i+1;

        boolean[] visited = new boolean[n];

        combination(arr, visited, 0, 0, k);

        return answer;
    }
}

조합 Combination

서로 다른 n 개 중 순서없이 r 개를 뽑는 것 , 일종의 dfs 를 이용한 재귀이자 백트래킹

• 중복은 허용되지 않아, visited 로 방문여부를 체크한다.
• 방문하지 않은 인덱스를 방문했다고 체크하고 현재 원소보다 뒤의 원소에 대한 탐색을 하기 위해 start로 i+1, depth를 depth+1로 증가시키며 재귀로 진행한다.
• depth 가 지정한 r 과 같을 때 다 선택했다는 뜻이므로, 방문한 원소만 뽑아내고 다시 돌아가 진행한다.

public void combination(int[] arr, boolean[] visited, int start, int depth, int r){
	if(depth == r) {
    	for(int i = 0 ; i < arr.length ; i++){
        	if(visited[i]) System.out.print(arr[i]+" ")
            }
        }
        return;
    }
    
    for(int i = start ; i < arr.length ; i++){
    	if(!visited[i]){
			visited[i] = true;
            combination(arr, visited, i+1, depth+1, r);
            //현재 원소보다 뒤의 원소 탐색 -> i+1, depth+1
            visited[i] = false;
        }
    }
}

arr = [1,2,3,4] 

//2개 조합
[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]
=> 6개

중복 조합

서로 다른 n 개 중 순서없이, 중복이 가능하게 r 개를 뽑는 것

• 조합과 비슷하지만 이미 뽑은 것을 뽑을 수 있는 중복을 허용하기때문에 방문여부 체크를 위한 visited 가 필요없다.
• 현재 원소보다 뒤의 것만 선택하는 것이아니라, 현재 원소를 포함하여 그 뒤의 원소까지 탐색이 가능하기 때문에 start를 i로 변경하여 재귀를 호출시킨다.
• 선택한 원소를 저장하는 배열이 필요하다.

public void combinationWithDuplication(int[] arr, int[] out, int start, int depth, int r){
	if(depth == r){
    	//선택된 원소들이 저장된 배열 out 추출
        for(int num : out) System.out.println(num);
       	return;
    }
    for(int i = 0 ; i < arr.length; i++){
    	out[depth] = arr[i];
        combinationWithDuplication(arr, out, i, depth+1, r);
        //현재 원소를 깊이에 맞게 저장해두고
        //중복 가능하기 때문에 현재 원소부터 뒤의 원소까지 탐색 -> i, depth+1
    }
}

arr = [1,2,3,4] 
    
//2개 조합
[1,1]
[1,2]
[1,3]
[1,4]
[2,2]
[2,3]
[2,4]
[3,3]
[3,4]
[4,4]
=> 10개