[LeetCode] 078 Subsets

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

Subsets - LeetCode

 

1. Backtracking

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
    
private: 
    vector<vector<int>> result;
    vector<int> saved;
    void backtracking(vector<int>& nums, int index)
    {
        result.push_back(saved);
        for(int i=index; i<nums.size(); ++i)
        {
            saved.push_back(nums[i]);
            backtracking(nums, i+1);
            saved.pop_back();
        }        
    }
};

 

2. Iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};

        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]); 
                subs.back().push_back(num);
            }
        }
        return subs;
    }
};

 for 반복문을 돌면서 기존에 저장되어있는 값을 복사하여 새로 추가하고, 새로 추가할 때는 사용하지 않은 nums 입력값 하나를 추가한다.

 

[1,2,3]을 예시로 들 때

1. Initially, one empty subset [[]]
2. Adding 1 to []: [[], [1]];
3. Adding 2 to [] and [1]: [[], [1], [2], [1, 2]];
4. Adding 3 to [], [1], [2] and [1, 2]: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

참고

https://leetcode.com/problems/subsets/discuss/27278/C%2B%2B-RecursiveIterativeBit-Manipulation

C++ Recursive/Iterative/Bit-Manipulation - LeetCode Discuss

 

 

3. Bit Masking

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>>result;

        int total = 1<<nums.size();        
        for(int i=0;i<total;i++){
            int index = i;
            vector<int> temp;
            for(int j=0; index!=0; j++)
            {
                if(index&1){ temp.push_back(nums[j]); }
                index = index >> 1;            
            }
            
            result.push_back(temp);
        }
        return result;
    }
};

1. total : 입력값이 x개이면 출력값은 2^x(1<<x)개가 되어야 한다.

2. for 반복문을 total 개수만큼 돌면서 필요한 subset을 얻어낼 것이다.

 

nums[j]에서 j의 overflow

이때 j를 nums[j]에서 사용하므로 j<nums.size() 조건을 확인해주는 것이 맞다. 하지만 total을 통하여 우리는 nums.size()를 알고 있고. 이를 index로 저장하여 가지고 있다. for 반복문이 진행될 때 >>1 연산을 하므로, index==0일 때 j가 nums.size와 같거나 커질 염려는 없다.

 

3. index는 어느 bit를 사용할지 결정한다.

i       BitRepresentation       Array         Ans_Array 
0         [ 0 0 0 ]             []            {}                  ----->as There No Set Bit 

1         [ 0 0 1 ]            [ 0 0 3]       {1}  

2         [ 0 1 0 ]            [ 0 2 0]       {2}  

3         [ 0 1 1 ]            [ 0 2 3]       {1,2}  

4         [ 1 0 0 ]            [ 1 0 0]       {3}  

5         [ 1 0 1 ]            [ 1 0 3]       {1,3}  

6         [ 1 1 0 ]            [ 1 2 0]       {2,3}  

7         [ 1 1 1 ]            [ 1 2 3]       {1,2,3}

i가 4일 때 예를 들어보자. index는 차례대로 4->2->1->0이 된다. 이 때 bit mask( index & 1 )을 이용하므로 마지막 bit가 1인 숫자에서만 push_back()함수를 호출한다. 따라서 마지막 4,2,0일때는 push_back()함수를 호출하지 않는다.

이때 index가 1일 때 j=2이므로 nums[2]가 저장된다.

 

i가 7일 때 예를 들어보자. index는 차례대로 7->3->1->0이 된다. 이 때 bit mask( index & 1 )을 이용하므로 마지막 bit가 1인 상황에서만 push_back()이 호출된다. 7->3->1일 때 push_back()함수를 호출한다. 이때 nums[0], nums[1], nums[2]가 저장된다.

 

참고

예제로 든 BitRepresentation에 오류가 있다.

https://leetcode.com/problems/subsets/discuss/729863/C%2B%2B-Using-Bit-Masking-or-most-simpler-or-with-Explain

[C++] Using Bit Masking | most simpler | with Explain - LeetCode Discuss