78. Subsets

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

Subsets - LeetCode

 

정수 목록이 주어졌을 때, 해당 원소들로 구성할 수 있는 유니크한 조합 목록을 반환하는 문제다.

 

2가지 풀이 방법이 있다.

 

1. Recursive (Backtracking)

흔히 트리에서 left node와 right node를 순차적으로 방문할 때 재귀적으로 방문하듯이 목록에서도 동일하게 방문한다.

vector에서 push_back이랑 pop_back을 활용해 목록을 넣고 빼고 하면서 조합해 나간다.

{ 1

  { 1, 2

    { 1, 2, 3

  { 1, 3

{ 2

  { 2, 3

대략 이런식으로..

class Solution {
public:    
    void solve(vector<vector<int>>& ret, vector<int>& nums, vector<int>& sub, int n)
    {
        ret.push_back(sub);

        for (int i=n; i<nums.size(); ++i)
        {
            sub.push_back(nums[i]);
            solve(ret, nums, sub, i + 1);
            sub.pop_back();
        }
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        ret.reserve(pow(2, nums.size()));
        
        vector<int> sub;        
        solve(ret, nums, sub, 0);
        
        return ret;
    }
};

 

 

2. Bit Manipulation

주어진 정수는 조합에서 사용되거나 안되거나로 표현할 수 있고, 이는 0과 1의 bit로 표현할 수 있다.

예를 들어 [1,2,3]의 경우

1은 2개의 연속 집합 단위에 1번 나타나고

[], [1], //// [ ], [1   ], //// [ ], [1   ], //// [    ], [1      ]

2는 4개의 연속 집합 단위에 2번 나타나고

[], [1], [2], [1, 2], //// [ ], [1   ], [2   ], [1, 2   ]

3은 8개의 연속 집합 단위에 4번 나타난다.

[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

 

주어진 정수가 3개인 경우 총 8가지 경우의 수가 나오는데, 

[0] - 1, 3, 5, 7

[1] - 3, 4, 6, 7

[2] - 4, 5, 6, 7

 

라고하는데 이걸 어떻게 알아냈는지, i >> j 식을 어떻게 추론했는진 모르겠다 ㅡㅡ

 

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