[자바 알고리즘 인터뷰] 12장 그래프 (6) 부분집합

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

 

 

- 모든 부분집합을 리턴하라 

 

 

풀이 1) 트리의 모든 DFS 결과 

 

- 트리를 구성하고 트리를 DFS하는 문제로 풀이할 수 있다.

- 자기 자신보다 큰 값이 자식 노드인 트리형태가 된다. 

 

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

 

- path에 지금까지 탐색한 경로를 저장하며 인덱스를 증가시키면서 DFS한다. 

- 별도의 종료 조건없이 모든 탐색의 경로가 부분집합이 되므로 탐색할 때 마다 매번 결과를 추가하면 된다. 

 

public void dfs(List<List<Integer>> results, int nums[], int index, Deque<Integer> path)
{
    //모든 탐색 경로를 매번 결과에 추가
    results.add(new ArrayList<>(path));
    //자기 자신보다 큰 숫자를 DFS 진행
    for(int i=index; i<nums.length; i++)
    {
        //path에 현재 엘리먼트 추가
        path.add(nums[i]);
        //재귀 dfs
        dfs(results,nums,i+1, path);
        //돌아온 이후에는 현재 엘리먼트 삭제
        path.removeLast();
    }
}

 

 

 

class Solution {
    public void dfs(List<List<Integer>> results, int nums[], int index, Deque<Integer> path)
    {
        //모든 탐색 경로를 매번 결과에 추가
        results.add(new ArrayList<>(path));
        //자기 자신보다 큰 숫자를 DFS 진행
        for(int i=index; i<nums.length; i++)
        {
            //path에 현재 엘리먼트 추가
            path.add(nums[i]);
            //재귀 dfs
            dfs(results,nums,i+1, path);
            //돌아온 이후에는 현재 엘리먼트 삭제
            path.removeLast();
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        //결과 저장 리스트 선언
        List<List<Integer>> results = new ArrayList<>();
        //DFS 시작
        dfs(results, nums, 0, new ArrayDeque<>());

        return results;
    }
}

1밀리초