[Grind75-LeetCode] Subsets JAVA

반응형

728x90

[Grind75-LeetCode] Subsets - Medium

---

접근

• dfs

---

풀이

배열의 원소들을 중복 없이 조합 가능한 모든 조합을 찾는 문제이다. 비슷한 형태의 문제를 많이 풀었던 거 같은데 이 문제도 역시나 dfs를 사용해 모든 조합을 찾아주면 된다. 

   public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), nums, 0);
        return result;
    }

dfs 사용을 위해 결과 배열, 현재 사용 배열, 정수 배열, 시작 인덱스를 파라미터로 넘긴다.

    private void dfs(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            dfs(result, current, nums, i + 1); 
            current.remove(current.size() - 1); 
        }
    }

원소가 존재하지 않는 빈 배열도 조합으로 치기 때문에 비어있는 배열이 추가되며 시작된다. 현재 배열에 원소를 추가해 다음 단계로 넘기고 다시 원소를 제거해 다른 경로 탐색이 가능하게 해 준다. 기본적인 dfs의 원리를 따르며 간단한 코드로 풀어지는 문제이다. 

---

전체 코드

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), nums, 0);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            dfs(result, current, nums, i + 1); 
            current.remove(current.size() - 1); 
        }
    }
}