LeetCode: 78번 (Minimum Window Substring) [JAVA]

문제 링크

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

Subsets - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 결과를 저장할 List<List<Interger> result 를 초기화
2. 기본적인 빈 조합을 result에 추가
3. 이후 주어진 nums 배열 길이만큼 반복
   1) 현재 result에 저장된 부분 조합들의 개수를 저장
   2) 기존 result에 저장된 부분 조합들을 모두 복사해 새로운 List 생성 후, 현재 nums 요소만을 추가한 다음 result에 저장
   
4. 최종 result 반환

 주어진 nums 배열을 바탕으로, 만들 수 있는 모든 부분집합들을 만들어 반환하는 문제이다. 이를 만드는데 있어서 조합을 활용하여, 현재 주어진 nums 배열의 길이가 n이라고 하면, nC0 부터 nCn 까지의 숫자 조합을 모두 만들게 되면 모든 부분집합을 만들 수 있다.
 다만 이보다는 좀 더 간단한 로직으로 부분집합을 만들어 낼 수 있는데, 바로 nums에 요소가 하나씩 추가될 때마다 이전까지의 부분집합들을 바탕으로 재활용하는 방법이다. 결국 nums 배열을 바탕으로 모든 부분집합들을 생성했다고 했을 때, 만약 새로운 요소가 추가되며 새로운 부분집합들을 만들 때는 기존의 부분집합들에 새로운 요소만을 추가한 집합들을 추가만 해주면 된다.
 예를 들어, 우선 nums 배열이 없다고 했을 때, 만들어질 수 있는 부분집합은 공집합([])이 있다. 이후 만약 nums 배열에 요소 1이 추가 되면, 기본적으로 존재하는 공집합([])과 해당 집합에 요소 1을 추가한 집합([1])을 더해 ([], [1])이 최종 부분집합이 된다. 다시 nums 배열에 2를 추가하면 기존 부분집합([], [1])에 2를 추가한 ([2], [1, 2])를 더하여, 최종 ([], [1], [2], [1, 2])이 전체 부분집합이 되고, 이어 추가로 3이 더해지면 기존 부분집합([], [1], [2], [1, 2])에 3을 추가한 집합들인 ([3], [1, 3], [2, 3], [1, 2, 3])을 더하여 최종 ([], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3])이 전체 부분집합이 된다.
 이 개념을 활용하여 전체 부분집합을 생성하면 된다. 전체 부분집합들을 저장하여 반환할 List<List<Interger> result를  생성하여 초기화한 다음, 기본적인 공집합을 추가해준다. 그 다음 주어진 nums 배열 길이만큼 for문 반복을 진행한다. 현재 result에 저장된 부분조합들 개수를 파악한 다음, 해당 조합들 가져와 새로운 List<Integer>를 생성해준다. 그 다음 현재 추가할 요소를 새로운 List<Integer>에 추가하고 해당 List를 result에 추가해주면 된다. 이후 최종 result를 반환해주면 된다.

 

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());//기본적인 빈 조합 추가

        for (int i = 0; i < nums.length; i++) {//주어진 nums 배열 길이만큼 반복
            int size = result.size();//현재까지의 result 사이즈 저장

            for (int j = 0; j < size; j++) {//기존에 result에 저장된 조합들에 대해 반복
                List<Integer> temp = new ArrayList<>(result.get(j));//기존 조합을 복사 
                temp.add(nums[i]);//기존 조합에 현재 숫자만을 추가
                result.add(temp);//result에 저장
            }
        }

        return result;
    }
}

결과