Leetcode - 46. Permutations

문제

주어진 배열 요소의 모든 순열(순서대로 나열하는 경우의수)을 출력. (모든 값은 unique함이 보장)

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

풀이 - backtracking

nsize만큼의 배열을 모두 backtracking하는데, 만약 tmp배열에 이미 존재하면 skip. (이를 위해 tmp배열을 O(n)만큼 탐색해야함)

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
public:
    void back_tracking(vector<int> nums, int size) {
        if (size < 0)
            return;
        if (size == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // if nums[i] is already exist in nums[i]; then continue
            bool cont = false;
            for (int j = 0; j < tmp.size(); j++) { // O(n)
                if (tmp[j] == nums[i]) {
                    cont = true;
                    break;
                }
            }
            if (cont == true)
                continue;
            tmp.push_back(nums[i]);
            back_tracking(nums, size - 1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int nsize = nums.size();
        back_tracking(nums, nsize);
        return ret;
    }
};

풀이 - backtracking 개선

해시테이블을 사용하여 O(n)동안 tmp를 탐색했던 시간복잡도를 O(1)로 줄임. 대박적!!
주어진 문제의 입력의 배열크기가 최대 6이라서 실제 실행시간의 큰 이득은 없는데 만약 입력이 엄청 커지면 드라마틱하게 성능 향상이 있을것임.

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
    unordered_map<int, bool> tmp_map;
public:
    void back_tracking(vector<int> nums, int size) {
        if (size < 0)
            return;
        if (size == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // if nums[i] is already exist in nums[i]; then continue
            if (tmp_map[nums[i]] == true) // O(1) Wow!
                continue;
            
            tmp.push_back(nums[i]);
            tmp_map[nums[i]] = true;
            back_tracking(nums, size - 1);
            tmp_map[nums[i]] = false;
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int nsize = nums.size();
        back_tracking(nums, nsize);
        return ret;
    }
};

풀이

정확히 std::next_permutation 사용. (근데 이걸로 풀고 끝내면 공부 하나도 안된다. )

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;   
        std::sort(nums.begin(), nums.end());
        do {
            ret.push_back(nums);   
        } while(std::next_permutation(nums.begin(), nums.end()));
        return ret;
    }
};