[LeetCode] - 78. Subsets

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "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.

---

Example 1 :

Input : nums = [1,2,3]

Output : [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 

Example 2 :

Input : nums = [0]

Output : [[],[0]]

 

Constraints :

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

---

주어진 정수 배열 nums의 모든 부분 집합(멱집합)을 반환하는 문제입니다. 중복되는 부분 집합은 없어야 하며, 결과는 순서에 상관없이 반환될 수 있습니다. 예를 들어, 입력이 [1,2,3]인 경우, 가능한 모든 부분 집합을 반환해야 합니다.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int n = nums.length;
        int subsetL = (int) Math.pow(2, n);

        for (int i = 0; i < subsetL; i++) {
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    temp.add(nums[j]);
                }
            }
            res.add(temp);
        }

        return res;
    }
}

 

위 코드는 비트마스킹을 사용해봤습니다. 이 방식을 수업시간에 빠르게 배웠었던 기억이 났는데요. Power set 인가? 그런 거였는데... 정확한 명칭은 기억이 안 나는 점 양해해 주십시오... 궁금하시다면 제가 다시 한번 찾아보겠습니다. 댓글로 말해주세요! 이제 코드를 설명해 보겠습니다 : 

1. 부분 집합의 수 계산 :
   • 주어진 배열 nums의 길이 n에 대해 가능한 모든 부분 집합의 수는 2n2^n2n입니다.
2. 비트 마스킹을 사용하여 부분 집합 생성 :
   • i는 0부터 2n−12^n - 12n−1까지의 숫자를 나타내며, 각 숫자는 이진수로 부분 집합을 나타냅니다.
   • j는 배열 nums의 인덱스를 나타내며, i의 j번째 비트가 1인지 확인합니다.
   • j번째 비트가 1이면 nums[j]를 현재 부분 집합 temp에 추가합니다.
   • temp를 결과 리스트 res에 추가합니다.

시간 및 공간 복잡도 :

1. 시간 복잡도 :
   • 각 숫자 i에 대해 n개의 비트를 확인하므로, 시간 복잡도는 O(n * 2^n)입니다.
   • 여기서 n은 배열 nums의 길이이고, 2^n은 가능한 모든 부분 집합의 수입니다.
2. 공간 복잡도 :
   • 결과 리스트 res에는 모든 부분 집합이 저장되므로, 공간 복잡도는 O(n * 2^n)입니다.
   • 여기서 n은 각 부분 집합의 최대 길이이고, 2^n은 가능한 모든 부분 집합의 수입니다.
   •  

---

Runtime 결과