[LeetCode] 78. Subsets

LeetCode - 78. Subsets 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/subsets/

풀이

vector<int>& nums의 원소로 만들 수 있는 모든 부분 집합을 구하여 반환하는 문제이다.

, 개의 부분집합을 구하는 것은 충분히 실행될 수 있으므로 비트 연산을 활용하여 부분 집합을 구할 수 있다.

(i & (1 << j))의 결과가 0이 아닌 경우 j 위치의 원소를 뽑아야 하는 것을 의미한다.

소스 코드

class Solution {

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        const int N = (int)nums.size();
        const int LIMIT = 1 << N;
        for (int i = 0; i < LIMIT; ++i) {
            vector<int> sub;
            for (int j = 0; j < N; ++j) {
                if ((i & (1 << j)) != 0) {
                    sub.push_back(nums[j]);
                }
            }
            result.push_back(sub);
        }
        return result;
    }
};