[👍][BackTrack][Medium] 46. Permutations

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

 

정수 배열이 주어질 때, 가능한 모든 조합을 찾아라.

 

이 문제는 풀이 방법을 외우는 게 좋겠다.

각 문제별로 효과적으로 푸는 체계에 대한 정리가 즉, 알고리즘 풀이법이다. 

 

이 문제는 back tracking으로 접근해서 해결 할 수 있고, 

직접 구성하기 보다는, 과정에서 오는 값으로 각 원소를 swap해 주면 원하는 결과를 얻을 수 있게 된다. 

 

어떻게?

 

backtrack 과정에서 현재 index와 이동하는 index를 교환한다. 

 

코드 

void SwapPermute(vector<int>& vNum, int idx1, int idx2)
{
    if(idx1<0 || idx1>=vNum.size()) return;
    if(idx2<0 || idx2>=vNum.size()) return;

    int temp = vNum[idx1];
    vNum[idx1] = vNum[idx2];
    vNum[idx2] = temp;
}

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

    for(int q = idx; q < nums.size(); ++q)
    {
        SwapPermute(vCur, idx, q+1);       // 다음 수와 교체
        permuteBT(idx+1, vRet, vCur, nums);
        SwapPermute(vCur, idx, q+1);
    }
}

public:
vector<vector<int>> permute(vector<int>& nums) 
{
    vector<vector<int>> vRet;
    vector<int> vCur{nums};
    permuteBT(0, vRet, vCur, nums);
    return vRet;
}

 

 

결과