Gidhub BE Developer

LeetCode : 78. Subsets

2020-12-26
goodGid

78. Subsets

Problem

Given an integer array nums, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.

Example

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

[1] Code (20. 12. 26)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {

        List<Integer> list = new LinkedList<>();

        // Remove duplicate value
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }

        list = new LinkedList<>(new HashSet<>(list)); // [1]

        List<List<Integer>> ansList = new LinkedList<>();
        recursive(ansList, list, 0, new LinkedList<>());
        return ansList;
    }

    private void recursive(List<List<Integer>> ansList,
                           List<Integer> list,
                           int depth,
                           List<Integer> tempAnsList) {
        if (depth == list.size()) {
            ansList.add(new LinkedList<>(tempAnsList));
            return;
        }

        // Do choose
        tempAnsList.add(list.get(depth));
        recursive(ansList, list, depth + 1, tempAnsList);

        // Do not choose
        tempAnsList.remove(tempAnsList.size() - 1);
        recursive(ansList, list, depth + 1, tempAnsList);
    }
}
  • 대표적인 DFS 방식으로 풀이

  • [1] : List에서 중복된 값을 제거하는 코드


[2] Code (20. 12. 26)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> subsets = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> currentSubset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                int pos = 1 << j;
                if ((i & pos) >= 1) {
                    currentSubset.add(nums[j]);
                }
            }
            subsets.add(currentSubset);
        }
        return subsets;
    }
}
  • 단순 DFS 탐색이므로 비트 마스킹으로도 풀이가 가능하다.

    직접 손으로 해보면 충분히 이해가 가능하니 꼭 이해해서 습득하면 좋은 스킬이 될 거 같다.


Reference


Comments

Index