[Backtracking][Medium] 46. Permutations

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 배열 값 nums 가 있을 때, 이 배열로 조합 가능한 모든 조합을 출력하라.

 

Solution. 

 좋은 문제임과 동시에 실제 많이 접할 수 있는 문제. 

 

 모든 수 조합을 하나씩 넣어보고, 유일한 조합인지 확인후에 그렇다면 최종 리스트에 push 한다.

void permute_BT(vector<vector<int>>& vRet, vector<int>& nums, unordered_set<int>& sCur)
{
    // 최종적으로 목표 길이에 도달하면 중지한다.
    if (sCur.size() == nums.size())
    {
        vector<int> temp;
        unordered_set<int>::iterator it = sCur.begin();
        for (; it != sCur.end(); ++it)
            temp.push_back( nums[*it] );
        vRet.push_back(temp);
        return;
    }

    // 유일한 index만 push 한다.
    for (int k = 0; k < nums.size(); ++k)
    {
        if (sCur.find(k) != sCur.end())
            continue;
        sCur.insert(k);
        permute_BT(vRet, nums, sCur);
        sCur.erase(k);
    }
}

vector<vector<int>> permute(vector<int>& nums) 
{
    vector<vector<int>> vRet;
    unordered_set<int> sCur;
    permute_BT(vRet, nums, sCur);
    return vRet;
}

 

일단 해결은 된다. 

 

 

또 다른 방법으로는, 조금 생각을 바꿔서 

원소를 일일이 넣기 보다, 

순서대로 위치를 바꾸는 것을 생각해 볼 수 있다.

 

위치를 하나씩 증가하면서 배열 끝까지 바꾼다.

이때, 위치 변경은 원소 자체 변경이 없으므로, 여전히 그 값들은 입력시와 동일하게 유일하다.

따라서 중복 check 검사가 필요 없다.

void permute_swap(vector<int>& nums, int i, int j)
{
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
void permute_SwapBT(vector<vector<int>>& vRet, vector<int>& nums, int idx)
{
    if (idx >= nums.size())
    {
        vRet.push_back(nums);
        return;
    }

    for (int k = idx; k < nums.size(); ++k)
    {
        permute_swap(nums, idx, k);
        permute_SwapBT(vRet, nums, idx+1);
        permute_swap(nums, idx, k);
    }
}

vector<vector<int>> permute(vector<int>& nums) 
{
    vector<vector<int>> vRet;
    permute_SwapBT(vRet, nums, 0);
    return vRet;
}

 

조금 더 빠르게 잘 됨을 확인 할 수 있다.