[LeetCode] C++ 46. Permutations

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

 

문제

 

문제 분석

- DFS를 이용하되 요소를 넣다가 뺐다가 하면서 재귀적으로 반복하여 구현할 수 있습니다.

- next_permutation을 사용하여 구현할 수도 있습니다

 

문제 풀이 1 (DFS)

class Solution {
private:
    vector<vector<int>> result;
    vector<int> nums;
    vector<bool> used;

public:
    void dfs(vector<int>& current){
        if (current.size() == nums.size()){
            result.push_back(current);
            return;
        }

        for(int i = 0; i < nums.size(); ++i){
            if(used[i])
                continue;
            
            current.push_back(nums[i]);
            used[i] = true;
            dfs(current);
            current.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        this->nums = nums;
        used.resize(nums.size(), false);

        if(nums.empty()){
            return result;
        }

        vector<int> current;
        dfs(current);
        return result;
    }
};

 

문제 풀이 2 (DFS 최적화)

class Solution {
private:
    vector<vector<int>> result;

    void dfs(vector<int> &nums, int start){
        if(start == nums.size()){
            result.push_back(nums);
            return;
        }

        for(int i = start; i < nums.size(); ++i){
            swap(nums[start], nums[i]);
            dfs(nums, start+1);
            swap(nums[start], nums[i]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return result;
    }
};

 

문제 풀이 3 (next_permutation)

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;

        sort(nums.begin(), nums.end());

        do {
            result.push_back(nums);
        } while(next_permutation(nums.begin(), nums.end()));

        return result;
    }
};

• next_permutation은 배열을 뒤에서부터 탐색하여 처음으로 감소하는 부분을 찾고, 그 다음 배열을 뒤에서부터 다시 탐색하여 앞서 선택된 숫자보다 큰 숫자를 찾고 둘을 교환합니다. 교환된 부분 이후의 숫자들을 반대로 정렬하기에 맨 처음에 오름차순으로 정렬을 해야 합니다.