[Backtrack][Medium] 78. Subsets

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

Subsets - LeetCode

 

Q. nums 배열이 주어질때, blank를 포함한 해당 배열로 조합 가능한 모든 subset을 찾아라. 

 

 

Solution. 

 다시 한번 느끼지만, 어떤 알고리즘 문제든, 우선 어떤 틀에 녹여서 풀면 가장 효율적일지 찾는것이 풀이법의 가장 먼저일 것 같다.

 해당 문제도 특정 배열의 구성 조합, 재구성에 대한 질문으로 역시 backtrack이 풀이 알고리즘 구조로 적합하겠다.

 

 주어진 배열의 길이만큼 배열 원소를 접근 하여, 

 한번에 원소 중 하나를 선택한다. 

 

 current vector

 1

 1, 2

 1, 2, 3  <- 종료 시 hold vector. (nums와 같은 size) 

 종료 조건일 때, 찾은 data는 마지막 라인과 같다. 

 모든 subset은 이 도중의 모든 과정이 포함되어야 한다. 

 

 empty 

 1

 1, 2

 1, 2, 3 

 2

 2, 3 

 3 

 과정은 위와 같게 되며, 이는 모든 subset과 동일한다. 

 

 로직대로 코드를 쓴다.

 

void subsets_BT(vector<vector<int>>& vOut, vector<int>& nums, vector<int>& vCur, int idx)
{
    // 도중의 모든 과정을 push 한다.
    vOut.push_back(vCur);
    if (idx >= nums.size())
        return;

    for (int q = idx; q < nums.size(); ++q)
    {
        vCur.push_back(nums[q]);
        subsets_BT(vOut, nums, vCur, q + 1); // q+1이 다음 target이 됨에 유의.
        vCur.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) 
{
    vector<vector<int>> vOut;
    vector<int> vCur;
    subsets_BT(vOut, nums, vCur, 0);
    return vOut; 
}

 

 

적절한 결과를 얻었다.