[👍][BackTrack][Medium] 78. Subsets

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

 

주어진 정수 배열의 모든 subset들을 출력하라.

 

할 때마다 감이 안잡히는 걸 보니 좋은 문제가 확실! 

 

여러 방법이 있을 수 있겠으나, 일단 back tracking 형식으로 수를 모은다. 

back tracking의 주요 파라미터는 

* 종료 조건 

* loop의 재시작 index 지점

* 다음 back track으로 넘기는 index

 

등이다. 

따라서 위 세 값을 기본 backtrack 형식에 녹이고 잘 조절하면 답을 찾을 수 있다.

 

종료 조건 - 3개를 모으면 더 이상 하지 않는다.

loop의 재 시작 index 지점 - 전달 받는 index 다음에서 시작한다.

다음 backtrack으로 넘기는 index - 루프를 도는 index 다음부터 시작하도록 넘긴다. 

 

특이한 점은 모든 과정에 대해 결과를 push 해야 한다는 것이다.

 

코드 

void subsetsBT(vector<vector<int>>& vRet, vector<int>& vCur, vector<int>& nums, int idx)
{
    vRet.push_back(vCur);
    if (idx >= nums.size())                // 배열의 size를 넘기면 멈춘다
        return;

    for(int q = idx; q < nums.size(); ++q) // 전달받은 지점부터 다시 loop를 돈다. 
    {
        vCur.push_back(nums[q]);
        subsetsBT(vRet, vCur, nums, q + 1); // 다음 index에서 다음 backtrack이 시작되게 한다
        vCur.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) 
{
    vector<vector<int>> vRet;
    vector<int> vCur;
    subsetsBT(vRet, vCur, nums, 0);

    return vRet;
}

 

결과

 

 

 

위 방법은 뭔가 직관적이지 못하다. 

 

또 다른 방법은 decesion making 방법을 취하는 것이다. 

즉, 특정 원소의 값을 결과에 취하느냐 마느냐의 선택이 있고

그 모든 상태에 대해 back track을 해 나가는 것이다. 

이것은 backtrack 이라기 보다는 DP에 가깝다고 본다.

 

과정 tree ( https://www.youtube.com/watch?v=REOH22Xwdkk )

 

 

코드

void subsetsBT(vector<vector<int>>& vRet, vector<int>& vCur, vector<int>& nums, int idx)
{
    if (idx >= nums.size())
    {
        vRet.push_back(vCur);
        return;
    }

    // include the value.
    vCur.push_back(nums[idx]);
    subsetsBT(vRet, vCur, nums, idx + 1);
    vCur.pop_back();

    // exclude the value.
    subsetsBT(vRet, vCur, nums, idx + 1);
}

vector<vector<int>> subsets(vector<int>& nums) 
{
    vector<vector<int>> vRet;
    vector<int> vCur;
    subsetsBT(vRet, vCur, nums, 0);

    return vRet;
}

 

 

결과