[C++] LeetCode : Permutations

Question

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

integer 타입의 정수로 이루어진 배열이 주어졌을 때, 가능한 모든 순열을 return 하라. return 하는 순서는 상관없다. 

 

제약사항

• 배열의 길이는 1이상 6 이하
• 배열 각 원소의 값은 -10 이상 10 이하.
• 배열의 모든 원소는 unique 하다.

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 모든 순열을 순회하는 문제이다. 어떤 방식으로 하건 모든 원소는 최소 한 번씩은 조회해보아야 한다. 따라서 BCR은 O(n)이다.

고려사항

• BFS vs DFS? 

---

Solution1 (Bruth Force)

모든 순열을 조회해야 하기 때문에 BFS가 더 적합할 것 같다. visit 배열을 둬서 방문 여부를 체크한다. 

class Solution {
public:
    void make_permutation(vector<vector<int>>& ans, vector<int>& nums, vector<int> v, bool visit[6], int step) {
        if (nums.size() == step) {
            ans.push_back(v);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (visit[i] == false) {
                visit[i] = true;
                v.push_back(nums[i]);
                make_permutation(ans, nums, v, visit, step + 1);
                v.pop_back();
                visit[i] = false;
            }
        }

        return;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> v;
        bool visit[6] = { 0 };

        make_permutation(ans, nums, v, { 0 }, 0);

        return ans;
    }
};

• Time complexity : O(Sigma(P(N, K)) 여기서 P는 n 또는 부분 순열의 k 순열이다. 보다 형식적으로 P(N, k) = (N!)/(N-k)!)이다.
• Space Complexity : O(N!)  가능한 모든 Solution을 저장해두어야 하기 때문이다. N은 배열의 길이이다. 

visit 을 쓰지않고 index를 바꿔주는 swap 으로 푸는 방법도 있다. 

 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/795/

Explore - LeetCode