[자바 알고리즘 인터뷰] 12장 그래프 (4) 조합

https://leetcode.com/problems/combinations/description/

 

- 전체 수 n을 입력받아 k개의 조합(Combination)을 리턴하라 

 

 

풀이 1) DFS로 k개 조합 생성 

 

출처:자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

- 조합의 경우 자기 자신뿐만 아니라 앞의 모든 엘리먼트를 배제하고 구성해야 한다.

- 왜냐하면 조합은 순서를 보지 않으므로 한 번 나왔던 엘리먼트는 다시 나와야 하지 않기 때문이다. 

- 이 말은 이전 엘리먼트보다 이후 엘리먼트의 값을 항상 더 크게 구성할 수있다는 말이기도 하다. 

 

public void dfs(List<List<Integer>> results, LinkedList<Integer>elements, int n, int start, int k)
    {
        //k번째 노드에 도달하면 결과에 추가
        if(k==0) {
            results.add(elements.stream().collect(Collectors.toList()));
            return;
        }

        //현재 엘리먼트 이후 엘리먼트 탐색
        for(int i=start; i<=n; i++)
        {
            //전달받은 엘리먼트에 더해 현재 엘리먼트 추가
            elements.add(i);
            //재귀 dfs
            dfs(results,elements,n,i+1,k-1);
            //돌아온 이후에는 현재 엘리먼트 삭제
            elements.removeLast();
        }
    }

 

 

- dfs()는 현재 엘리먼트 이후 엘리먼트를 계속 탐색하여 재귀 호출하는데, elements 변수에는 이미 현재 엘리먼트 이전의 값이 담겨 있다. 

- 따라서 남아 있는 값끼리 나머지 조합을 수행하는 형태가 되며, k==0이 되면 목표한 k개 조합에 도달한 셈이므로 결과에 삽입한다. 

 

 

class Solution {
    public void dfs(List<List<Integer>> results, LinkedList<Integer>elements, int n, int start, int k)
    {
        //k번째 노드에 도달하면 결과에 추가
        if(k==0) {
            results.add(elements.stream().collect(Collectors.toList()));
            return;
        }

        //현재 엘리먼트 이후 엘리먼트 탐색
        for(int i=start; i<=n; i++)
        {
            //전달받은 엘리먼트에 더해 현재 엘리먼트 추가
            elements.add(i);
            //재귀 dfs
            dfs(results,elements,n,i+1,k-1);
            //돌아온 이후에는 현재 엘리먼트 삭제
            elements.removeLast();
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        //결과 저장 리스트 선언
        List<List<Integer>> results = new ArrayList<>();
        //dfs 시작
        dfs(results, new LinkedList<>(),n,1,k);

        return results;
        
    }
}

62밀리초