[LeetCode] 78. Subsets

 

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

leetcode - Subsets

문제 유형 : dfs, 백트래킹, 재귀, 비트마스킹

문제 난이도 : Medium

 

문제

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.

 

중복이 없는 요소들의 정수 배열 nums가 주어진다. 모든 부분집합을 만드시오.

중복된 부분집합을 허용하지 않습니다.

순서는 상관 없습니다.

 

풀이

백트래킹 풀이 - 빈 배열부터 시작해서 이번 인덱스의 숫자를 넣고 재귀호출하고 제거한다.

 

비트마스킹 풀이 - https://riveroverflow.tistory.com/entry/LeetCode-1863-Sum-of-All-Subset-XOR-Totals

[LeetCode] 1863. Sum of All Subset XOR Totals

의 O(2^n * n)풀이를 참고하라.

비트마스킹을 통해서 각 요소를 넣는지에 대한 여부를 0 또는 1로 나타낸다고 생각하면 된다.

 

코드

C++ - 백트래킹 풀이

class Solution {
private:
    vector<vector<int>> ans;
    int n;
public:
    void dfs(vector<int>& nums, vector<int> &arr, int idx) {

        ans.push_back(arr);
        for(int i = idx; i < n; i++) {
            arr.push_back(nums[i]);
            dfs(nums, arr, i+1);
            arr.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        vector<int> s = {};
        dfs(nums, s, 0);
        return ans;
    }
};

C++ - 비트마스킹 풀이

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        int m = 1 << n;
        vector<vector<int>> ans;
        for(int i = 0; i < m; i++) {
            vector<int> tmp;
            for(int j = 0; j < n; j++) {
                if(i & (1 << j)) tmp.push_back(nums[j]);
            }
            ans.push_back(tmp);
        }

        return ans;
    }
};