.leetcode(78. Subsets)

문제

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

문제 풀기 전

1. rescursive하게 풀되 중간중간에 저장하면 되겠다.
2. 예전에 Permutations처럼 구하되, 중간중간에 저장만 잘하면 되겠는걸.

직접 푼 풀이

소요시간: 15분(10:46 ~ 11:01)

class Solution {
    private Set<List<Integer>> result = new HashSet<>();
    public List<List<Integer>> subsets(int[] nums) {
        result.add(new ArrayList());
        doSubSets(nums, 0, new int[nums.length]);
        return result.stream().collect(Collectors.toList());
    }

    private void doSubSets(int[] nums, int index, int[] made) {
        if (index == nums.length) {
            return;
        }

        List<Integer> temp = new ArrayList<>();
        for (int i=0; i<nums.length; i++) {
            int next = nums[i];
            if (next == -11) {
                continue;
            }

            temp.add(next);
            nums[i] = -11;
            made[i] = next;
            doSubSets(nums, index+1, made);
            nums[i] = next;
        }

        result.add(temp);  
    }
}

느낀점

1. 풀긴 풀었는데 조금 지저분한 감이 없지 않아 있다.
2. iteratvie하게 기존 부분집합을 갑지고 그대로 2배씩 커지는 집합을 만들 수도 있다.
3. 기가막힌 풀이는 bitmask를 이용한 풀이였다. 모든 bit를 출력할 수 있는 마법의 공식을 기억해둘 필요가 있다

솔루션 공부 후 추가로 푼 풀이

#2배씩 커지는 풀이
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++) {
            List<List<Integer>> sub = new ArrayList<>();
            for(List<Integer> each: result) {
                List<Integer> copy = new ArrayList<>();
                for (Integer inner: each) {
                    copy.add(inner);
                }
                copy.add(nums[i]);
                sub.add(copy);
            }

            for (List<Integer> each: sub) {
                result.add(each);
            }
        }

        return result;
    }
}

#bitmask를 이용한 풀이
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int nthBit = 1 << nums.length;
        for (int i=0; i < nthBit; i++) {
            String bitmask = Integer.toBinaryString(i | nthBit).substring(1);

            List<Integer> sub = new ArrayList<>();
            for (int j=0; j<bitmask.length(); j++) {
                if (bitmask.charAt(j) == '1') {
                    sub.add(nums[j]);
                }
            }
            result.add(sub);
        }

        return result;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• 백트래킹으로 풀어보기
• 비트마스크로 풀어보기