78. Subsets

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

 

Given an integer array nums of unique elements, return all possible 
subsets
 
(the power set)
.

The solution set must not contain duplicate subsets. Return the solution in any order.

 

배열이 주어질 때, 해당 배열의 모든 부분집합을 리턴하는 문제였다. (공집합 포함)

해당 문제를 풀면서 느꼈던 것은 자바의 List 인터페이스 메서드에 대해서 잘 모르고 쓰고있구나 하는 생각이 들었다. 

문제를 풀다가 List<Integer> 형태에 Integer 값인 nums[i]를 추가했더니 

error: incompatible types: boolean cannot be converted to List<Integer>

 

형이 달라서 에러 메세지가 계속 떴다. boolean을 리턴하는게 없는데 왜 자꾸 해당 에러가 발생하는가 싶어 인터넷을 보았더니 List의 add 메서드의 리턴 타입은 boolean이라고 한다.

dfs(list.add(nums[i]); 이런식으로 재귀함수를 실행시켜 주고 있었는데, 해당 방식이 아니라

cur.add(nums[i]);
dfs(nums, cur, i + 1);

 

먼저 리스트에 값을 추가하고, boolean 값을 반환한 뒤에 해당 리스트를 가지고 재귀함수를 돌리면 해결 되었다.

또한, 최종값에 현재 값들을 더해줄 때 

// List<List<Integer> res;
// List<Integer> cur;
res.add(cur);

 

이런식으로 계속 더해주려고 했지만, 최종 결과값엔 모두 빈 배열을 리턴해주고 있었다.

 

이거는 Java의 리스트가 참조 동작하기 때문에 cur를 수정하는 경우에 res에 저장된 값도 영향을 받기 때문에 원본에 영향이 가지 않도록 해야했다. 따라서, 새로운 리스트(복사본)을 만들어 res에 넣어주는 것으로 해결 가능했다.

res.add(new ArrayList<>(cur));

 

 

전체 코드

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }

        dfs(nums, new ArrayList<>(), 0);
        return res;
    }

    public void dfs(int [] nums, List<Integer> cur, int depth) {
        res.add(new ArrayList<>(cur));

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

 

백트래킹으로 해결 가능한 문제였지만, 자바의 리스트가 익숙하지 않아서 해멨다.